说明

国庆节就要结束了，张同学帮别人养猫的时间就要结束啦，猫猫真的超可爱，张同学超喜欢，有点舍不得就想着给猫猫买一些糖果可以留着以后吃吃。

糖果有N种，张同学的袋子体积是V，多了就装不下了，张同学为了猫猫不在乎自己的money，希望能买到最多并且最值钱的糖果，张同学最后只想知道买的糖果到底值多少钱，所以只需要输出一个整数。（为了猫猫不惜代价，冲冲冲！）

N种糖果有大有小，有贵有便宜，还有的限量

糖果有三类：

1：第一类糖果只能买一颗；

2：第二类糖果可以随便购买；

3：第三类糖果最多买Si颗。

每种糖果对应体积是Vi，价值是Wi；

输入格式

第一行两个整数，N，V，用空格隔开，分别表示糖果种数和袋子体积。

接下来有N行，每行三个整数Vi，Wi，Si，用空格隔开，分别表示第i种糖果的体积，价值和数量。

1，Si=-1表示第i种糖果只能买一颗；

2，Si=0表示第i种糖果随便买；

3，Si>0表示的i种糖果最多买Si颗。

输出格式

输出一个整数，表示购买糖果花的money。

样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

8

提示

0<N<100,0<=V<=10000

0<Vi，Wi<=1000

-1<=Si<=10000