Background

Remember the King's Game from NOIP 2012 Senior Group Day1? Time flies, and two years have passed. The King's Game is outdated now, replaced by the Queen's Game. Please solve a similar problem to the King's Game.

Problem Description

The Queen has $n$ ministers, each with a positive integer written on both their left and right hands. As the National Day approaches, the Queen decides to award bonuses to these $n$ ministers. The bonus for the $i$-th minister is the greater of the bonus received by the $(i-1)$-th minister and the sum of the numbers on the left hands of the first $i$ ministers, plus the number on the $i$-th minister's right hand.

Formally, let the positive integer on the left hand of the $i$-th minister be $a_i$, and on the right hand be $b_i$. The bonus for the $i$-th minister, $c_i$, can be expressed 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} $$

The thrifty Queen does not want to distribute too many bonuses, so she asks you to rearrange the order of the ministers to minimize the maximum bonus awarded.

Note: Rearranging the order does not necessarily mean shuffling the sequence; you are allowed to keep the positions of the ministers unchanged.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

Next, $T$ parts follow. Each part starts with a positive integer $n$, indicating the number of ministers.

The next $n$ lines in each part contain two positive integers each, $a_i$ and $b_i$, as described above.

Output Format

Output $T$ lines, each containing an integer representing the maximum bonus received by a minister.

Sample Input and Output

Input Sample #1

1
3
4 1
2 2
1 2

Output Sample #1

8

Input Sample #2

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

Output Sample #2

528
902

Notes

Arranging the ministers in the order $1,2,3$ results in the minister with the highest bonus receiving $10$.

Arranging them in the order $1,3,2$ results in the highest bonus being $9$.

Arranging them in the order $2,1,3$ results in the highest bonus being $9$.

Arranging them in the order $2,3,1$ results in the highest bonus being $8$.

Arranging them in the order $3,1,2$ results in the highest bonus being $9$.

Arranging them in the order $3,2,1$ results in the highest bonus being $8$.

When arranged in the order $3,2,1$, the numbers on the hands of the ministers are:

$(1,2),(2,2),(4,1)$.

• The first minister receives a bonus of $1+2=3$.
• The second minister receives a bonus of $\max{3,3}+2=5$.
• The third minister receives a bonus of $\max{5,7}+1=8$.

For all test cases, it is guaranteed that $T \leq 10$, $1 \leq n \leq 2 \times 10^4$, and $1 \leq a_i, b_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分