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

---

【问题描述】

　　有 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(v[i]\)、价值为 \(p[i]\)、数量有 \(s[i]\) 个。选一些物品装入一个容量为 \(C\) 的背包，使得价值尽量大。

【输入格式】

　　第 1 行是整数 \(N\) 和 \(C\)，表示有 \(N\) 种物品，背包的容量为 \(C\)。
　　接下来的 \(N\) 行，每行三个整数：\(v[i]\)、\(p[i]\) 和 \(s[i]\)，表示物品 \(i\) 的体积、价值和数量。

【输出格式】

　　一个整数，表示能得到的最大价值。

【输入输出样例1】

　Input

3 7
2 3 12
3 5 15
1 2 3

　Output

12

【数据限制】

　　\(1≤N≤100\)
　　\(0<C≤100000\)
　　\(0<v[i]≤100\)
　　\(0<P[i]≤1000\)
　　\(0<s[i]≤500\)

【来源】

　Mr.he