Background

Special for beginners, ^_^

Description

你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下 $V$ 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 $G$。

现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。

Format

Input

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

第二行：$N$ 表示拿到 $N$ 件礼物。

第三到 $N+2$ 行：每行 $3$ 个数 $T_i, V_i, G_i$ 表示各礼物的完美值、重量和体积

Output

输出共一个数，表示可能获得的最大完美值。

Samples

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

50

Limitation

1s, 1024KiB for each test case.

对于 $20\%$ 的数据 $N,V,G,T_i,V_i,G_i\le 10$；

对于 $50\%$ 的数据 $N,V,G,T_i,V_i,G_i\le 100$；

对于 $80\%$ 的数据 $N,V,G,T_i,V_i,G_i\le 300$；

$80\%$ 到 $100\%$ 的数据是 $N,V,G,T_i,V_i,G_i\le 380$ 的离散随机数据。