该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

《TEMPLE RUN》是小菜最喜欢玩的一款跑酷手游。一名冒险家来到古老的庙宇中寻宝，却碰上怪兽的追赶。玩家所需要做的动作只是转弯、跳跃和向后卧倒，需要翻过古庙围墙,爬上悬崖峭壁,在此过程中，你可以晃动设备收集金币。游戏操作很简单易懂，只需要一只手就能玩，但是它又如此困难，任何一个失误你都需要从头再来。

这天游戏里新引入了一个角色——大佐，他将和小菜一起参与逃亡。然而大佐身上带满了各种没用的东西，现在他需要把许多的东西塞进小菜的神奇背包里，但是尽管小菜的背包很神奇，大小却也有所限制，只能够放进非常重要的物品。现在大佐把自己各个物品的数量、体积与重要值告诉了小菜，而小菜又不善于计算这些，为了防止被坑，小菜需要你帮他计算出怎么样的组合方式能使背包的价值最大。

输入格式

第一行有$2$个整数，物品种数n和背包总体积$v$。

第$2$行到$i+1$行每行$3$个整数，为第$i$种物品的数量$m$、体积$w$、重要值$s$。

输出格式

仅包含一个整数，即为能拿到的最大的价值总和。

样例

输入数据 1

2 10
3 4 3
2 2 5

输出数据 1

13

提示

【注释】

选第一种一个，第二种两个。结果为3*1+5*2=13

【数据规模】

对于$100$的数据，$1<=v<=500$，$1<=n<=2000$，$1<=m<=5000$，$1<=w<=20$，$1<=s<=100$。