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

---

【题目描述】

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

　　物品一共有三类：

　　第一类 物品只能用 1 次（01背包）；
　　第二类 物品可以用无限次（完全背包）；
　　第三类 物品最多只能用 \(s[i]\) 次（多重背包）；
　　每种体积是 \(v[i]\)，价值是 \(w[i]\)。

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

【输入格式】

　　第一行两个整数：\(N，C\)，用空格隔开，分别表示物品种数和背包容积。
　　接下来有 \(N\) 行，每行三个整数 \(v[i],w[i],s[i]\)，用空格隔开，分别表示第 \(i\) 种物品的体积、价值和数量。
　　　\(s[i]=−1\) 表示第 \(i\) 种物品只能用 1 次；
　　　\(s[i]=0\) 表示第 \(i\) 种物品可以用无限次；
　　　\(s[i]>0\) 表示第 \(i\) 种物品可以使用 \(s[i]\) 次；

【输出格式】

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

【输入输出样例】

　Input

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

　Output

8

【数据限制】

　　\(0<N,C≤1000\)
　　\(0<C≤10000\)
　　\(0<vi,pi≤1000\)
　　\(−1≤s[i]≤1000\)

【来源】

　　Mr.he