问题描述
2045年的SD省队选拔，赛制和三十年前已是完全不同。一场比赛的比赛时间有 $t$ 分钟，有 $n$ 道题目。
第 $i$ 道题目的初始分值为 $A_i(A_i \leq 10^{6})$ 分，之后每过一分钟这道题目的分值会减少 $B_i$ 分，并且保证到比赛结束时分值不会减少为负值。比如，一个人在第 $x$ 分钟结束时做出了第 $i$ 道题目，那么他/她可以得到 $A_i - B_i * x$ 分。
若一名选手在第 $x$ 分钟结束时做完了一道题目，则他/她可以在第 $x+1$ 分钟开始时立即开始做另一道题目。
参加省队选拔的选手 dxy 具有绝佳的实力，他可以准确预测自己做每道题目所要花费的时间，做第 $i$ 道需要花费 $C_i(C_i \leq t)$ 分钟。由于 dxy 非常神，他会做所有的题目。但是由于比赛时间有限，他可能无法做完所有的题目。他希望安排一个做题的顺序，在比赛结束之前得到尽量多的分数。
输入描述
第一行为一个正整数 $T(T \leq 10)$，表示数据组数($n>200$的数据不超过$5$组)。
对于每组数据，第一行为两个正整数 $n (n \leq 1000)$ 和 $t (t \leq 3000)$, 分别表示题目数量和比赛时间。接下来有 $n$ 行，每行 $3$ 个正整数依次表示 $A_i, B_i, C_i$，即此题的初始分值、每分钟减少的分值、dxy做这道题需要花费的时间。
输出描述
对于每组数据输出一行一个整数，代表dxy这场比赛最多能得多少分
输入样例
1
4 10
110 5 9
30 2 1
80 4 8
50 3 2
输出样例
88
Hint
dxy先做第二题，再做第一题，第一题得分为$110-5*(1+9)=60$，第二题得分为$30-2*1=28$，总得分为$88$，其他任何方案的得分都小于$88$
