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

题目背景

学长们整了一个三角洲私服！（假的）

亮亮学长专业堵桥，可是不是很爽，于是他想起了父亲的话：要合理利用管理员身份……（真有个实例）

于是亮亮学长就“稍微”调了一下他的SR-25的伤害（也就摁了七八个0），于是不一会儿就有了一地学长的盒子（其他学长：[○･｀Д´･ ○]）。

但是亮亮学长不会理包，但他想知道最大收益是多少，只好把任务交给你。
亮亮学长在私服里有哈夫克空间压缩技术，可以将$x$格的收集品变成占$x$个单位空间（无视形状）的压缩包，而他的包——“口袋空间”更是能装很多个单位空间的压缩包。
虽然你可能讨厌堵桥，但请你写个程序帮帮亮亮学长。

题目说明

在学长盒子里共翻出了$n$种物品，亮亮学长的“口袋空间”共计有$m$个单位空间。
亮亮学长技术先进，转化无需时间。
对于每种物品，都会有对应的数量$num_i$、体积$v_i$和价值$a_i$，其中$i(1\le i\le n)$

因为要跑到飞升撤离，亮亮学长没有时间慢慢理包，请你在一秒内求出最大收益。

输入格式

第$1$行两个整数$n$,$m$表示物品种类和空间大小

第$2$~$n+1$每行三个整数$num、v、a$，表示$i(1\le i\le n)$号物品的数量、格数和价值。

输出格式

输出一个整数$ans$，表示理包后的最大收益。

样例

3 6
1 1 3
1 2 5
1 4 7

12

4 100
4 5 10
2 11 25
5 17 62
1 70 111

340

数据范围

对于测试点$1$~$10$，保证：

• $\sum_{i=1}^{n}num_i \le10^4$
• $m\times\sum_{i=1}^{n}num_i \le 2\times10^7$

对于测试点11（彩蛋点）：$\sum_{i=1}^{n}num_i \le10^5$且$m=5\times10^3$

对于所有测试点：$0\le ans\le 2147483648$

由于是私服，我加个$114514$格大红不过分吧^_^