logo AlgoBeat OnlineJudge
登录 注册

#201099. 皇后游戏

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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


皇后有 位大臣,每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临,皇后决定为 位大臣颁发奖金,其中第 位大臣所获得的奖金数目为第 位大臣所获得奖金数目与前 位大臣左手上的数的和的较大值再加上第 位大臣右手上的数。

形式化地讲:我们设第 位大臣左手上的正整数为 ,右手上的正整数为 ,则第 位大臣获得的奖金数目为 可以表达为:

当然,吝啬的皇后并不希望太多的奖金被发给大臣,所以她想请你来重新安排一下队伍的顺序,使得获得奖金最多的大臣,所获奖金数目尽可能的少。

注意:重新安排队伍并不意味着一定要打乱顺序,我们允许不改变任何一位大臣的位置。

输入格式

第一行包含一个正整数 ,表示测试数据的组数。

接下来 个部分,每个部分的第一行包含一个正整数 ,表示大臣的数目。

每个部分接下来 行中,每行两个正整数,分别为 ,含义如上文所述。

输出格式

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

样例

样例输入 1

1
3
4 1
2 2
1 2

样例输出 1

8

样例输入 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

样例输出 2

528
902

数据范围与提示

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

按照 这样排列队伍,获得最多奖金的大臣获得奖金的数目为

当按照 这样排列队伍时,三位大臣左右手的数分别为:

  • 位大臣获得的奖金为
  • 位大臣获得的奖金为
  • 位大臣获得的奖金为

对于全部测试数据满足: