2027: 旅行准备

【问题描述】

每个人小时候都有自己的理想，但随着时间推移，渐渐的大多数人的理想变成了金钱.地位.面子... 于是大多数人 就变成了传说中的俗人。

但我们的中中始终有自己的梦想，他要环游世界！ 在20XX年X月X日中中开始环游世 界的准备工作.他开始准备自己的行囊

中中背包的容积为m ，中中有n样有用的东西 ，每样东西都有自己的价值Wi，和体积Vi ，每一样物品有Ni个 （Ni=0时表示有无限多个），于是乎我们的问题就是（你应该已经猜到了）...中中能带走的 东西的最大价值。

【输入格式】

第 1 行: N,M--物品的种类和背包的容积 
第 2-N+1 行: Vi，Wi，Pi--三个整数:每个物品的体积.价值.个数

【输出格式】

单独的一行在给定的限制里可能得到的最大的价值。

【输入样例】

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

【输出样例】

106

【数据约束】

单独的一行在给定的限制里可能得到的最大的价值。

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

106