说明

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

输入格式

[md] 第1行有2个整数N,M，表示物品的种类和背包的容积； 第2-N+1行，每行有3个整数Vi，Wi，Pi，分别表示每个物品的体积，价值，个数。 （体积<=5000,价值<=5000,个数<=1000） [/md]

输出格式

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

样例

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

106

提示

[md] 30%数据满足  1 <= m,n <=1000 100%数据满足  1 <=m,n <= 10000 [/md]