多重背包

有 $n$ 种物品和一个容量是 $m$ 的背包，第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$，数量是 $s_i$。

问能装入背包的最大价值是多少。

输入格式： 第一行两个整数 $n,m$；接下来有 $n$ 行，每行三个整数 $v_i,w_i,s_i$。

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

数据范围：

• #1-#5：$0<n≤1000,0<m,v_i,w_i,s_i≤100$
• #6-#8：$0<n≤1000,0<m,v_i,w_i,s_i≤2000$
• #9-#15：$0<n≤1000,0<m,v_i,w_i,s_i≤20000$
• #16-#20：$0<n≤1000,0<m,v_i,w_i,s_i≤40000$

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

10