飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16762

题意：给你n个服务，然后每个服务有时间di，和执行时间si，如果执行后的时间超过di，则惩罚值为max(0,最终的时间-di)，求最大两个惩罚值相加最小。

分析：二分套二分套二分，复杂度logn*n*logn*n。。。ORZ

第一个二分是确定两个和最小值用的，假设当前检测的值是x，则我们枚举每个服务，然后第二个二分，二分x的值，且l要大于等于x/2向上取整，r为x，这个是为了确定两个其中一个比较大的值，那么另一个值就可以为x-大的值，然后第三个二分，用来确定k应该插入到哪里去，假设大的值为i，小的值为j，则每个服务的d值都得家j，但是k的d值要加i，应该能理解，然后不是属于k的我们只要排序一次就够了，因为加了跟没加排序不变，然后用第三个二分把k插进去，按更新后的d从小到大，why??因为d越大的话，它的可用区域越大，贪心~所以把小的先处理，如果当前执行的任务超过了当前的d，如果是k，那就是说明k更新的值太小，所以第二个二分的l=mid+1，如果不是k，且超过了，那个r=mid-1，k太大~，如果可以，那么就说明当前方案是可以的，更新第一个二分。。。最后输出，over，啪啪啪，AC~

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#define LL long long
using namespace std;
const int maxn=5*123;
struct he
{
    int s,d;
} JLJ[maxn];
int T,n;
bool cmp(he a,he b)
{
    return a.d<b.d;
}
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d%d",&JLJ[i].s,&JLJ[i].d);
}
vector<he> V;
int isOK(int x,int y,int idx)
{
    int l=0;
    int r=V.size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(V[mid].d+y>JLJ[idx].d+x)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    V.insert(V.begin()+l, JLJ[idx]);
    int ip=l;
    int before=0;
    for(int i=0; i<V.size()-1; i++)
    {
        int tm=y;
        if(i==ip)tm=x;
        int s=V[i].s;
        int d=V[i].d+tm;
        if(s+before>d)
        {
            V.erase(V.begin()+ip);
            if(i==ip)return 1;
            return 2;
        }
        else before+=s;
    }
    V.erase(V.begin()+ip);
    return 0;
}
bool check(int x)
{

    for(int i=1; i<=n; i++)
    {
        V.erase(V.begin()+i-1);
        int l=x/2;
        int r=x;
        if(x%2!=0)l++;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int t=isOK(mid,x-mid,i);
            if(t==0)
            {
                V.insert(V.begin()+i-1,JLJ[i]);
                return 1;
            }
            if(t==1)
            {
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        V.insert(V.begin()+i-1,JLJ[i]);
    }
    return 0;
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    V.clear();
    for(int j=1; j<=n; j++)
    {
        V.push_back(JLJ[j]);
    }
    he a;
    a.s=0;
    a.d=2000000000;
    V.push_back(a);
    int l=0;
    int r=1000000;
    int MIN=1000000000;
    while(l<=r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            MIN=min(mid,MIN);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}