该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

德国放松对英国的进攻后，把矛头指向了东边――苏联。1943 年初，东线的战斗进行到白热化阶段。据可靠情报，90 余万德国军队在库尔斯克准备发动浩大攻势。因此，朱可夫元帅要求你立即从远东的军工厂运 输大量装备支援库尔斯克前线。

列车司机告诉你，一趟列车最多可以容纳 V 体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载 G 单位的重量。

同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。

Format

Input

第一行：V 和 G 表示最大重量和体积。

第二行：N 表示仓库有 N 件装备。

第三行到 N+2 行：每行 3 个数 Ti Vi Gi 表示各装备的火力值、体积和重量。

Output

输出一个数，表示可能获得的最大火力值。

Samples

6 5
4
10 2 2
20 3 2
40 4 3
30 3 3

50

Limitation

对于 50%的数据，V,G,N≤100；

对于 100%的数据，V,G,N≤400；