题目描述

张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包啦。张老师有一个容积为$m$的背包，有$n$个物品作为放入背包的待选物品，每样东西都有自己的价值$W_i$，和体积$V_i$，第$i$个物品有$N_i$个（$N_i=0$时表示有无限多个），请你编程帮助张老师计算，他的背包能够存入的最大价值是多少？

输入描述

第1行有2个整数$N,M$，表示物品的种类和背包的容积； 第2~N+1行，每行有3个整数$V_i，W_i，P_i$，分别表示每个物品的体积，价值，个数。 （体积$<=5000$,价值$<=5000$,个数$<=1000$）

输出描述

一个整数，表示能够存入背包的最大价值。

用例

输入

5 50
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3

输出

106

数据范围

30%数据满足 $1 <= m,n <=1000$ 100%数据满足 $1 <=m,n <=10000$