比赛得分(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$ 题的最高得分、递减因子以及通过该题需要的时间。

输出格式

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

样例输入 #1

3 20
100 2 6
30 1 8
80 3 5

样例输出 #1

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$，即小爱能在考试时间内解决所有问题。

知识点与难度

本题涉及的知识点从属于 GESP 5级（贪心、排序），难度等级：⭐⭐⭐。

测试点分布