宝岛

作为船长的你，现在来到了一个宝岛，宝岛上有银锭、珍珠、金戒指、古玩、字画、钻石等一系列奇珍异宝。每种宝贝有三个属性，分别是重量 $w$、价值 $v$、数量 $s$；遗憾的是，你的船舱载重量有限，所以只能带走一部分宝贝，不然，就会沉船了！ 那么，把哪些宝贝搬进船舱，可以使得总价值最大、并且不超载呢？

输入格式

第一行含 $N$ 种宝物与船舱最大载重M，用空格隔开 $（1≤N≤10^2，1≤M≤10^5）$。 接下来 $N$ 行,每行三个整数 $w、v、s$，分别表示第i种宝物的重量、价值、数量 $（ 1≤w,c,s≤10^3 ）$

输出格式

一个整数，表示在不超载的情况下，可以获得的最高总价值。

3 13
2 4 8
3 7 2
4 10 1

29

提示

样例解释

理论上，选3个3号物品可以达到最大价值30； 但是很可惜，3号物品只有1个；故采取如下方案： 1号物品(2,4)选3个，重量为6，价值为12 2号物品(3,7)选1个，重量为3，价值为7 3号物品(4,10)选1个，重量为4，价值为10 总价值为29达到最大，总重量为13刚好不超载

时间限制: 1000ms

内存限制: 1MB