#D17020. 多重背包(2)

多重背包(2)

题目描述

有NN种物品和一个容量是VV的背包。

第ii种物品最多有sis_i件,每件体积是viv_i,价值是wiw_i。

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

输出最大价值。

输入描述

第一行两个整数,NN,VV,用空格隔开,分别表示物品种数和背包容积。

接下来有NN行,每行三个整数vi,wi,siv_i,w_i,s_i,用空格隔开,分别表示第ii种物品的体积、价值和数量。

输出描述

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

数据范围:

0<N≤10000 \lt N \le 1000,0<V≤20000 \lt V \le 2000,0<vi,wi,si≤20000 \lt v_i,w_i,s_i \le 2000。

样例

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