Codeforces Scoreboard

### 题目描述 你在参加一场有 $n$ 题的 CF 比赛。 解决每道题你都需要恰好 $1$ 分钟，提交时间可忽略不计。任何时刻你都只能解决最多一道题。第 $0$ 分钟比赛开始，故你可以在任何 $t\ge 1$ 时刻提交。假设你的提交一定通过。 每道题有三个参数 $k_i,b_i$ 和 $a_i$，表示在第 $t$ 时刻解决该题会得到 $\max(a_i,b_i-k\cdot t)$ 的分数。 你需要合理安排解决题目的顺序以得到最高的分数。比赛时间可看作能够完成所有题目。 ### 输入格式 输入第一行一个正整数 $t$（$1\le t\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 2\cdot 10^5$）表示题目数量。 接下来 $n$ 行，每行三个正整数 $k_i,b_i,a_i$（$1\le k_i,b_i,a_i\le 10^9$，$a_i < b_i$），含义见题目描述。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 输出格式 每组测试数据输出一行一个正整数表示能获得的最大分数。 ### 样例解释 第二组测试数据中，每个时刻每道题的分数如下表。标红的数字表示得到最高分 $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}$ |

You are participating in a Codeforces Round with $ n $ problems. You spend exactly one minute to solve each problem, the time it takes to submit a problem can be ignored. You can only solve at most one problem at any time. The contest starts at time $ 0 $ , so you can make your first submission at any time $ t \ge 1 $ minutes. Whenever you submit a problem, it is always accepted. The scoring of the $ i $ -th problem can be represented by three integers $ k_i $ , $ b_i $ , and $ a_i $ . If you solve it at time $ t $ minutes, you get $ \max(b_i - k_i \cdot t,a_i) $ points. Your task is to choose an order to solve all these $ n $ problems to get the maximum possible score. You can assume the contest is long enough to solve all problems.

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of problems. The $ n $ lines follow, the $ i $ -th of them contains three integers $ k_i $ , $ b_i $ , $ a_i $ ( $ 1\le k_i,b_i,a_i\le 10^9 $ ; $ a_i < b_i $ ), denoting that you get the score of $ \max(b_i - k_i \cdot t,a_i) $ if you solve the $ i $ -th task at time $ t $ minutes. It's guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ .

For each test case, print a line containing a single integer — the maximum score you can get.

4
4
10000 1000000000 2006
10000 1000000000 9999
2 999991010 1010
1000000000 1000000000 999999999
6
1 8 1
9 29 4
2 14 3
4 13 1
2 19 5
10 12 5
8
4 10 1
4 19 8
1 14 3
4 15 6
2 9 6
1 11 10
2 19 12
4 19 14
10
5 12 7
5 39 12
2 39 11
3 23 15
5 30 11
3 17 13
5 29 14
3 17 11
3 36 18
3 9 8

3999961003
53
78
180

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 $ .