Description

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

Input Format

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 Format

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

1
3
4 1
2 2
1 2

8

2
5
85 100
95 99
76 87
60 97
79 85
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

528
902

Hint

• 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