比赛得分(Contest Score)

题目描述

在一场时长为 $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$ 题的最高得分、递减因子以及通过该题需要的时间。

输出格式

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

数据范围

• 对于 30% 的数据，$1\leq n \leq 10$
• 对于 70% 的数据，$1\leq n \leq 10^3$
• 对于 100% 的数据，$1\leq n \leq 10^5$
• $1\leq s \leq 10^9,1 \leq a_i \leq 10^{12},1 \leq b_i \leq 10^3, 1\leq t_i \leq 10^4$
• 保证 $b_i \times s \le a_i$，即每题得分不会变成负数
• 保证 $\sum_{i=1}^n t_i \le s$，即小爱能在考试时间内解决所有问题。

样例输入 #1

3 20
100 2 6
30 1 8
80 3 5

样例输出 #1

154

样例说明 #1

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

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布