Codeforces Scoreboard
Contest: TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3300
Tags: binary search, data structures, dp, geometry

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.

Input format:
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$$$.

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
3999961003
53
78
180

Editorial:
Since $$$\max\{b_i-k_i\cdot t,a_i\} = b_i - \min\{k_i\cdot t, b_i - a_i\}$$$, we can pre-calculate the sum of $$$b_i$$$. Let $$$c_i = b_i - a_i$$$. Now our mission is to minimize the sum of $$$\min\{k_i\cdot t, b_i - a_i\}$$$.
If we assume $$$\min\{k_i\cdot t, b_i - a_i\} = k_i\cdot t$$$ for some $$$i$$$, sort these problems in descending order of $$$k_i$$$, then assign $$$1,2,3,\ldots$$$ to their $$$t$$$ in order. For $$$\min\{k_i\cdot t, b_i - a_i\} = b_i - a_i$$$, they can be directly calculated.
There comes a DP solution: Let $$$f_{i,j}$$$ be the minimum sum, when considering first $$$i$$$ problems (after sorting), $$$j$$$ problems of them satisfying $$$\min\{k_i\cdot t, b_i - a_i\} = k_i\cdot t$$$.
$$$$$$ f_{i,j}=\left\{ \begin{aligned} f_{i-1,j}+c_i & & j=0 \\ \min\{f_{i-1,j}+c_i,f_{i-1,j-1}+k_i\cdot j\} & & j>0 \end{aligned} \right. $$$$$$
The time complexity is $$$O(n^2)$$$.
We can find that $$$f_{i,j}$$$ is convex. Proof below:
Let $$$g_{i,j}=f_{i,j}-f_{i,j-1}$$$.
Thus $$$f_{i,j}=f_{i,0}+\sum\limits_{k=1}^jg_{i,k}$$$, rewrite this formula with the original recursive formula.
Then $$$$$$f_{i,0}+\sum_{k=1}^{j}g_{i,k}=\min\{f_{i-1,0},\sum_{k=1}^{j}g_{i-1,k}+c_i,f_{i-1,0}+\sum_{k=1}^{j-1}g_{i-1,k}+k_i\cdot j\}$$$$$$ $$$$$$c_i+\sum_{k=1}^{j}g_{i,k}=\sum_{k=1}^{j-1}g_{i-1,k}+\min\{g_{i-1,j}+c_i,k_i\cdot j\}$$$$$$ Let $$$j-1$$$ be $$$j$$$ $$$$$$c_i+\sum_{k=1}^{j-1}g_{i,k}=\sum_{k=1}^{j-2}g_{i-1,k}+\min\{g_{i-1,j-1}+c_i,k_i\cdot (j-1)\}$$$$$$ Subtract the above two formulas from each other $$$$$$g_{i,j}=g_{i-1,j-1}+\min\{g_{i-1,j}+c_i,k_i\cdot j\}-\min\{g_{i-1,j-1}+c_i,k_i\cdot (j-1)\}$$$$$$
Because $$$k$$$ is monotone non-increasing, so we can use mathematical induction to proof that for $$$j$$$, the increase speed of $$$g_{i-1,j}$$$ is faster than that of $$$k_i\cdot j$$$. We can find a critical value $$$M$$$ that $$$\forall j\le M, g_{i,j}<k_i\cdot j$$$ and $$$\forall j>M,g_{i,j}>k_i\cdot j$$$.
So compared $$$g_i$$$ with $$$g_{i+1}$$$, the first part of the sequence remains unchanged, and the last part is added with $$$k_i$$$, with an additional number $$$k_i\cdot j$$$ in the middle, where $$$j$$$ is the maximum number satisfied $$$g_{i-1,j-1}\le k_i \cdot j$$$.
Use the treap to maintain this sequence, which might be called the slope trick.