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

---

【题目描述】

　　有 \(N\) 种物品和一个容量是 \(C\) 的背包。

　　第 \(i\) 种物品最多有 \(s[i]\) 件，每件体积是 \(v[i]\)，价值是 \(p[i]\)。

　　求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

【输入格式】

　　第一行两个整数：\(N，C\)，分别表示物品种数和背包容积。
　　接下来有 \(N\) 行，每行三个整数 \(v[i],p[i],s[i]\)，用空格隔开，分别表示第 \(i\) 种物品的体积、价值和数量。

【输出格式】

　　输出一个整数，表示最大价值。

【输入输出样例】

　Input

4 5
1 2 3
2 4 1
3 4 3
4 5 2

　Output

10

【数据限制】

　　\(N≤1000\)
　　\(0<C≤50000\)
　　\(0<v[i],p[i],s[i]≤20000\)
　　 提示：本题考查多重背包的单调队列优化方法。

【来源】

　　Mr.he