说明

张老师准备环游世界，出发之前要做的最重要的事情，当然是整理自己的背包啦。张老师有一个容积为$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$，分别表示每个物品的体积，价值，个数。（体积$\leqslant 5000,价值\leqslant 5000,个数\leqslant 1000$）

输出格式

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

样例

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

106

数据范围

• 30%数据满足$1 \leqslant m,n \leqslant 1000$
• 100%数据满足$1 \leqslant m,n \leqslant 10000$