该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

${Steve}$ 准备远征MN。现在有许多的东西要放到 ${Steve}$ 的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品，现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值， ${Steve}$ 会非常地感谢你。

Format

Input

（1）第一行有 ${2}$ 个整数，物品种数 ${n}$ 和背包装载体积${v}$。

（2）2行到 ${n+1}$ 行每行 ${3}$个整数，为第 ${i}$ 种物品的数量 ${m}$、体积 ${w}$ 、价值 ${s}$。

Output

输出仅包含一个整数，即为能拿到的最大的物品价值总和。

Samples

2 10 
3 4 3
2 2 5

13

Limitation

${0<n<=2000,0<v<=500}$。答案在 ${int}$ 范围里