P2123 Queen's Game

Do you still remember the NOIP 2012 Senior Day 1 "King's Game"? Time flies — two years have passed. The King's Game is now outdated and has been replaced by the Queen's Game. Please solve another problem similar to the King's Game.

The queen has $n$ ministers. On each minister’s left and right hands, a positive integer is written. As the National Day approaches, the queen decides to award bonuses to the $n$ ministers. For the $i$-th minister, the bonus amount equals the larger of the previous minister’s bonus and the sum of the numbers on the left hands of the first $i$ ministers, then plus the number on the right hand of the $i$-th minister. Formally, let the positive integer on the left hand of the $i$-th minister be $a_i$, and the one on the right hand be $b_i$. The bonus received by the $i$-th minister is $c_i$, defined as: $$ c_{i} = \begin{cases} a_{1}+b_{1} & ,i=1 \\ \displaystyle \max \left \{ c_{i-1},\sum_{j=1}^{i}a_{j} \right \} +b_{i} & ,2\leq i \leq n \end{cases} %  $$ Of course, the frugal queen does not want too much bonus to be given. She asks you to reorder the queue so that the maximum bonus obtained by any minister is as small as possible. Note: Reordering the queue does not mean you must change the order. Keeping every minister in their original position is allowed. Constraints: For all testdata, $T \le 10$, $1 \le n \le 2 \times 10^{4}$, $1 \le a_i, b_i \le 10^{9}$.

The first line contains a positive integer $T$, the number of testdata groups. Then for each of the $T$ parts, the first line contains a positive integer $n$, the number of ministers. In each of the next $n$ lines, there are two positive integers $a_i$ and $b_i$, as defined above.

Output $T$ lines. Each line contains one integer: the maximum bonus obtained by any minister.

- If the queue is ordered as 1, 2, 3, the maximum bonus obtained by any minister is 10. - If the queue is ordered as 1, 3, 2, the maximum bonus obtained by any minister is 9. - If the queue is ordered as 2, 1, 3, the maximum bonus obtained by any minister is 9. - If the queue is ordered as 2, 3, 1, the maximum bonus obtained by any minister is 8. - If the queue is ordered as 3, 1, 2, the maximum bonus obtained by any minister is 9. - If the queue is ordered as 3, 2, 1, the maximum bonus obtained by any minister is 8. When the queue is ordered as 3, 2, 1, the numbers on the three ministers’ left and right hands are: (1, 2), (2, 2), (4, 1). - The 1st minister’s bonus is $1 + 2 = 3$. - The 2nd minister’s bonus is $\max{3, 3} + 2 = 5$. - The 3rd minister’s bonus is $\max{5, 7} + 1 = 8$. Translated by ChatGPT 5