时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有 \(N\) 个物品，第 \(i\) 个物品的体积为 \(v_i\)，重量为 \(w_i\)，价值为 \(p_i\)。选一些物品装到一个最大容量为 \(C\)，最大承重量为 \(G\) 的背包，问如何选择装入背包的物品，使得装入背包的物品的总价值尽量大。

【输入格式】

　　第一行包含三个整数：\(C、G\) 和 \(N\)。
　　接下来的 \(N\) 行，每行三个整数 \(v_i、w_i、p_i\)。

【输出格式】

　　包含一行一个整数，表示背包所装物品的最大价值。

【输入输出样例】

　Input

8 10 5
3 3 4
2 1 3
4 2 7
8 3 5
6 8 9

　Output

12

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤100\)，\(1≤v_i,w_i,p_i≤100\)，\(1≤C,G≤2000\)。

【来源】

　　Mr.he