皇后游戏

还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

皇后有 $n$ 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 $n$ 位大臣颁发奖金，其中第 $i$ 位大臣所获得的奖金数目为第 $i - 1$ 位大臣所获得奖金数目与前 $i$ 位大臣左手上的数的和的较大值再加上第 $i$ 位大臣右手上的数。 形式化地讲：我们设第 $i$ 位大臣左手上的正整数为 $a_i$，右手上的正整数为 $b_i$，则第 $i$ 位大臣获得的奖金数目为 $c_i$ 可以表达为： $$ 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} %  $$ 当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。 注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

第一行包含一个正整数 $T$，表示测试数据的组数。 接下来 $T$ 个部分，每个部分的第一行包含一个正整数 $n$，表示大臣的数目。 每个部分接下来 $n$ 行中，每行两个正整数，分别为 $a_i$ 和 $b_i$，含义如上文所述。

共 $T$ 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

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

按照 $1,2,3$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $10$； 按照 $1,3,2$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$； 按照 $2,1,3$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$； 按照 $2,3,1$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $8$； 按照 $3,1,2$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$； 按照 $3,2,1$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $8$。 当按照 $3,2,1$ 这样排列队伍时，三位大臣左右手的数分别为： $(1,2),(2,2),(4,1)$。 - 第 $1$ 位大臣获得的奖金为 $1+2=3$； - 第 $2$ 位大臣获得的奖金为 $\max{3,3}+2=5$； - 第 $3$ 为大臣获得的奖金为 $\max{5,7}+1=8$。 对于全部测试数据满足：$T\le10$，$1\le n\le 2\times 10^4$，$1\le a_i,b_i\le 10^9$。