Description

一年一度的学校运动会马上要开始了，为了激烈班上运动员的士气，班主任决定让杨某去买些奖品回来(奖品尽可能丰富)。杨某的背包可容纳物体的体积和可承载物体的重量都有限，如果载过重的物品，包带子会断裂...如果硬要塞入比标准可容纳体积大的物体，那背包就会裂开...

每件奖品都有各自的体积、重量以及价值。

在告诉你背包能装下体积和重量的最大值的情况下，请你求出能买回奖品的最大价值。

Format

Input

第一行：两个数 可容纳体积最大值 v(v<400)和承载重量最大值 m(m<400);

第二行：一个数 奖品总数 N(<50).

第三行至第 3+N 行:每行三个数 体积 vi(vi<400) 重量 mi(mi<400) 奖品价值(wi<500).

Output

一行：一个数，即所能达到的最大价值。

Samples

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

550

Limitation

1s, 1024KiB for each test case.