背景

2025csp复赛已过，成绩也已发布。

题目描述

FISH 复赛考得不好，非常伤心。结果与 RTY 人民对比更抑郁了。于是善良的你决定安慰 FISH。

FISH 现在的伤心程度是 $m$，你需要尽可能地安慰 FISH，但不能超过这个程度，否则 FISH 会以为你敷衍塞责，反而更加伤心了。PPCQ 现在准备了 $n$ 种安慰 FISH 的方法，每一种方法都只能用一定的次数，否则就对 FISH 没用了。还有，每一种方法都能安慰 FISH，减少一定的伤心度，且会额外对 FISH 产生一定的开心度。具体的：第 $i$ 种方法会对 FISH 安慰 $a_i$ 点伤心度，产生 $b_i$ 点开心度，且第 $i$ 种方法只能用 $c_i$ 次。

现在你需要找到一种方法，使 FISH 产生最多的开心度，且不让 FISH 更加伤心。你需要输出这个开心度。

输入输出

输入

输入共 $n+1$ 行。

• 第一行：两个整数，分别为 $n, m$。含义如题。
• 接下来 $n$ 行：每行三个整数，分别为 $a_i,b_i,c_i$。

输出

输出共一行。表示安慰 FISH 能得到的最大的开心值。

样例

4 20
3 9 3
5 9 1
9 4 2
8 1 3

47

数据范围

• 对于 $40\%$ 的数据：$0\le n,m\le 10^3$；
• 对于 $100\%$ 的数据：$0\le n,m\le 10^4;a_i,b_i,c_i\le 10^5$。