CF1787H Codeforces Scoreboard

你在参加一场有 $n$ 题的 CF 比赛。 解决每道题你都需要恰好 $1$ 分钟，提交时间可忽略不计。任何时刻你都只能解决最多一道题。第 $0$ 分钟比赛开始，故你可以在任何 $t\ge 1$ 时刻提交。假设你的提交一定通过。 每道题有三个参数 $k_i,b_i$ 和 $a_i$，表示在第 $t$ 时刻解决该题会得到 $\max(a_i,b_i-k\cdot t)$ 的分数。 你需要合理安排解决题目的顺序以得到最高的分数。比赛时间可看作能够完成所有题目。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。

输入第一行一个正整数 $t$（$1\le t\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 2\cdot 10^5$）表示题目数量。接下来 $n$ 行，每行三个正整数 $k_i,b_i,a_i(1\leq k_i,b_i,a_i\leq 10^9;a_i

每组测试数据输出一行一个正整数表示能获得的最大分数。 ### 样例解释 第二组测试数据中，每个时刻每道题的分数如下表。标红的数字表示得到最高分 $53$ 分的一种方法： | 时间 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 第 $1$ 题 | $7$ | $6$ | $5$ | $\color{red}{4}$ | $3$ | $2$ | | 第 $2$ 题 | $\color{red}{20}$ | $11$ | $4$ | $4$ | $4$ | $4$ | | 第 $3$ 题 | $12$ | $10$ | $\color{red}{8}$ | $6$ | $4$ | $3$ | | 第 $4$ 题 | $9$ | $5$ | $1$ | $1$ | $\color{red}{1}$ | $1$ | | 第 $5$ 题 | $17$ | $\color{red}{15}$ | $13$ | $11$ | $9$ | $7$ | | 第 $6$ 题 | $5$ | $5$ | $5$ | $5$ | $5$ | $\color{red}{5}$ |

In the second test case, the points for all problems at each minute are listed below. Time $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ Problem $ 1 $ $ 7 $ $ 6 $ $ 5 $ $ \color{red}{4} $ $ 3 $ $ 2 $ Problem $ 2 $ $ \color{red}{20} $ $ 11 $ $ 4 $ $ 4 $ $ 4 $ $ 4 $ Problem $ 3 $ $ 12 $ $ 10 $ $ \color{red}{8} $ $ 6 $ $ 4 $ $ 3 $ Problem $ 4 $ $ 9 $ $ 5 $ $ 1 $ $ 1 $ $ \color{red}{1} $ $ 1 $ Problem $ 5 $ $ 17 $ $ \color{red}{15} $ $ 13 $ $ 11 $ $ 9 $ $ 7 $ Problem $ 6 $ $ 5 $ $ 5 $ $ 5 $ $ 5 $ $ 5 $ $ \color{red}{5} $ The points displayed in red denote one of the optimal orders with the score $ 53 $ .