#P100020. 远征

远征

Description

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

Format

Input

(1)第一行有 2{2} 个整数,物品种数 n{n} 和背包装载体积v{v}

(2)2行到 n+1{n+1} 行每行 3{3}个整数,为第 i{i} 种物品的数量 m{m}、体积 w{w} 、价值 s{s}

Output

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

Samples

2 10 
3 4 3
2 2 5
13

Limitation

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