学步园

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::greater;

const int MAXN(510);

struct NODE
{
	int c, d;
	friend bool operator < (const NODE &op1, const NODE &op2)
	{
		return op1.d < op2.d;
	}
};

NODE node[MAXN];

void input(int n)
{
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &node[i].c, &node[i].d);
}

int solve(int n)
{
	sort(node, node+n);
	int ans, c1 = 0, c2 = 0, p = 0;
	int now = 0;
	for(int i = 0; i < n; ++i)
	{
		now += node[i].c;
		int temp = max(0, now-node[i].d);
		if(temp > c1)
		{
			c2 = c1;
			c1 = temp;
			p = i;
		}
		else
			if(temp > c2)
			{
				c2 = temp;
				p = i;
			}
	}
	ans = c1+c2;
	for(int i = 0; i < p; ++i)
	{
		now = c1 = c2 = 0;
		for(int j = 0; j < n; ++j)
		{
			if(j == i)
				continue;
			now += node[j].c;
			int temp = max(0, now-node[j].d);
			if(temp > c1)
			{
				c2 = c1;
				c1 = temp;
			}
			else
				if(temp > c2)
				{
					c2 = temp;
				}
			if(j == p)
			{
				now += node[i].c;
				temp = max(0, now-node[i].d);
				if(temp > c1)
				{
					c2 = c1;
					c1 = temp;
				}
				else
					if(temp > c2)
					{
						c2 = temp;
					}
			}
		}
		ans = min(ans, c1+c2);
	}
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		input(n);
		printf("%d\n", solve(n));
	}
	return 0;
}