closefrom

题目思路
乍一看，这题和NOIP 2012 提高组 Day1 的国王游戏很像，做题方法应该也差不多，找出一个排序方法，使得以这样排序得到的序列会使最大的c_ci最小。观察可知，c_i是逐渐递增的。我们用相邻交换法考虑。设某个位置上的大臣编号为i，后面一位大臣的编号为j。设i前面所有大臣的a值之和为x，i前面那一位大臣的c值为y。若不交换，则c值较大的大臣的c值（c_j）为
max(max(y,x+ai)+bi,x+ai+aj)+bj
化简后：max(y+bi+bj,x+ai+bi+bj,x+ai+aj+bj) => 没有交换，的最后一位的c值
同理，这两位大臣交换后c值较大的为后面那位
max(y+bi+bj,x+aj+bi+bj,x+ai+aj+bi) =>交换后，的最后一位的c值
假设不交换更优，则有
max(y+bi+bj,x+ai+bi+bj,x+ai+aj+bj) <= max(y+bi+bj,x+aj+bi+bj,x+ai+aj+bi)
发现两边都有y+bi+bj可以削去，数学上是不能削掉的，这题可以，则有：
max(x+ai+bi+bj,x+ai+aj+bj) <= max(x+aj+bi+bj,x+ai+aj+bi)
然后削去x,
max(ai+bi+bj,ai+aj+bj) <= max(aj+bi+bj,ai+aj+bi)
再化简：
max(bi,aj)+ai+bj <= max(bj,ai)+aj+bi
移项后：
max(bi,aj)-aj-bi <= max(bj,ai)-ai-bj
观察左项，aj,bi中大的那位会被削掉，也就是剩下一个最小的数的相反数，
用代码表示为：-min(aj,bi),那么右项同理可得结果：
-min(aj,bi) <= -min(ai,bj)
再把负号处理一下得到最终表达式：
min(ai,bj) <= min(aj,bi)

由于要创建结构体来存储x,y，还要对结构体排序，
则要重载运算符，不能重载小于等于，不然会有几个点RE，然后进行排序，
排序完成后，只需要模拟求出每个数得c值就可以了

z=> 前z位大臣左手和为x 第z位大臣c值为y

i {max(x+ai,y)+bi}第i位的c值
j max(max(x+ai,y)+bi,x+ai+bi)+bj 第j位的c值

不交换i j

i j 交换位置

j {max(x+aj,y)+bj} 第j位的c值
i {max(max(x+aj,y)+bj,x+aj+ai)+bi} 第i位的c值

交换i j

//My AC Code：
#include <cstdio>
#include <algorithm>
using namespace std;
int t,n;
long long tn[20005];
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a>b?a:b;}
struct node{
    int x,y;
    bool operator < (node a) const{
        return min(x,a.y)<min(y,a.x);
    }
}nn[20005];
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d",&n);
        long long s=0;
        for(int i=1;i<=n;i++)scanf("%d%d",&nn[i].x,&nn[i].y);
        sort(nn+1,nn+n+1);
        for(int i=1;i<=n;i++){
            s+=nn[i].x;
            tn[i]=max(s,tn[i-1])+nn[i].y;
        }
        printf("%lld\n",tn[n]);
    }
    return 0;
}