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

题目描述

在一场时长为 $s$ 的比赛中，有 $n$ 道题，第 $i$ 道题有一个最高得分 $a_i$ 和一个递减因子 $b_i$。

$a_i$ 是第 $i$ 题的最高得分，比赛开始后每过一分钟，该题得分就会减少 $b_i$。当一道题通过后，选手该题的得分即为确定。选手的整场考试的总得分为选手每题的得分之和。

假设小爱需要花费 $t_i$ 分钟才能解决第 $i$ 道问题。请问：如何安排做题顺序，能让该场考试的得分最高？

输入格式

第一行：两个整数 $n$ 与 $s$，表示该场考试题目数量和比赛时长；

接下来 $n$ 行，第 $i$ 行三个正整数 $a_i, b_i, t_i$，表示第 $i$ 题的最高得分、递减因子以及通过该题需要的时间。

输出格式

单个整数，表示可能获得的最高分数。

3 20
100 2 6
30 1 8
80 3 5

154

样例解释

先做第3题，在第5分钟时做完，得分为 $80-3×5=65$ 再做第1题，在第11分钟时做完，得分为 $100-2×11=78$ 再做第2题，在第19分钟时做完，得分为 $30-1×19=11$ 此时，总得分 $65+78+11=154$ 分。

数据规模与约定

对于 $30$% 的数据，$1 \le n \le 10$

对于 $70$% 的数据，$1 \le n \le 10^3$

对于 $100$% 的数据：$1 \le n \le 10^5$,$1 \le s \le 10^9$,$1 \le a_i \le 10^{12}$,$1 \le b_i \le 10^3$,$1 \le t_i \le 10^4$

保证 $b_i \times s \le a_i$，即每题得分不会变成负数。

保证 $\sum_{i=1}^{n} t_i \le s$，即小爱能在考试时间内解决所有问题。