You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

有 N 种物品，第 i 种物品的体积是 $c_i$，价值是 $w_i$，每种物品的数量都是有限的，为 $n_i$。 现有容量为 V 的背包，请你放入若干物品，在总体积不超过 V 的条件下，使总价值尽可能大。

输入格式

输入的第一行，两个整数N、V，表示 有 N 件物品 $(1 \leq N \leq 10000)$ 。 接下来N行，每行两个整数$w_i$、$c_i$、$n_i$，表示第 i 件物品的体积是 $c_i$，价值是 $w_i$,数量有$n_i$个

输出格式

输出包括一行，仅一个整数， 为背包中最多可以放入的物品总价值。

样例输入

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

样例输出

14