CF1787H.Codeforces Scoreboard

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.

你正在参加一场有 $n$ 道题的 Codeforces 比赛。

每道题恰好花费你一分钟来解决，提交题目所需的时间可忽略不计；在任意时刻你最多只能解决一道题。比赛从时间 $0$ 开始，因此你的第一次提交最早可在 $t \ge 1$ 分钟时进行。每次你提交一道题，该题总会被接受。

第 $i$ 道题的得分规则由三个整数 $k_i$、$b_i$ 和 $a_i$ 表示：若你在 $t$ 分钟时解决该题，则获得 $\max(b_i - k_i \cdot t,a_i)$ 分。

你的任务是选择一个解题顺序，使得所有 $n$ 道题的总得分最大。你可以假定比赛时间足够长，足以解决全部题目。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示题目的数量。

接下来 $n$ 行，其中第 $i$ 行包含三个整数 $k_i$、$b_i$、$a_i$（$1\le k_i,b_i,a_i\le 10^9$；且 $a_i \lt b_i$），表示：若你在第 $t$ 分钟解决第 $i$ 道题目，则获得的分数为 $\max(b_i - k_i \cdot t,a_i)$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一行，包含一个整数——你能获得的最高分数。

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

在第二个测试用例中，每道题目在每一分钟的得分如下所示：

时间

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

标为红色的得分表示一种最优解顺序，其总得分为 $53$。