爱新觉罗★XHM踏上了新征程。她到了零元购超市,打算看看怎么置备物资。
XHM有一个背包,大小是$k$。
零元购超市里有$n$类不同的物品,包括金子,银子,沙子等。
第$i$类物品数量是有限的,只有$a_i$个,每个单位占用书包大小$b_i$,每个单位价值为$c_i$。
$XHM$碍于有限的智商的确想不出问题的答案,她已经到商店里面了,大清PD马上过来,因此你赶紧给她算算最多能零元购价值多少的物资。
爱新觉罗★XHM踏上了新征程。她到了零元购超市,打算看看怎么置备物资。
XHM有一个背包,大小是$k$。
零元购超市里有$n$类不同的物品,包括金子,银子,沙子等。
第$i$类物品数量是有限的,只有$a_i$个,每个单位占用书包大小$b_i$,每个单位价值为$c_i$。
$XHM$碍于有限的智商的确想不出问题的答案,她已经到商店里面了,大清PD马上过来,因此你赶紧给她算算最多能零元购价值多少的物资。
第一行输入两个数字, $n$和$k$。$(1\leqslant n,k \leqslant 2\times 10 ^ 3)$
后面n行,每行输入三个数字, $a_i,b_i,c_i$。$(1\leqslant b_i,c_i \leqslant 2\times 10 ^ 6,1\leqslant a_i \leqslant 2\times 10 ^ 2)$
输出一个数字,XHM最多购入的物品价值。
输入
3 5 1 2 3 2 2 2 3 3 3
输出
6