有$N$种物品和一个容量为$V$的背包。每种物品均有有限多件，第$i$种物品所占空间是$c_i$，价值是$w_i$，数量是$num_i$。求解将哪些物品装入背包可使价值总和最大

输入格式

第一行为两个整数$N，V$($0 \leq V \leq 1000,0 \leq N \leq 100$)表示物品数量,背包的容量

接下来$N$行，每行有三个整数$C，W，NUM$($0 \lt C \leq 1000，0 \lt V \leq 100,0 \lt NUM \leq 10$)表示每种物品的所占空间和价值和数量

输出格式

一行一个整数，表示最大价值总和

样例

样例输入

4 10
3 15 2
4 6 1
2 4 1
1 6 3

样例输出

48

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32768\mathrm{KB}$