Untitled

#include<iostream>
using namespace std;
#define min(a, b) a < b ? a : b
#define INF 100000000
#define MAX 25
int N;
int infor[MAX][2];
int visited[MAX];
int ans, s0, s1, s2;

void backtrack(int k, int csum)
{
	int add, cnt;
	add = 0; 
	if(csum >= ans)
		return;
	if(k == N)
	{
		ans = min(ans, csum);
		return;
	}
	for(int i = 0; i < 3; i++)
	{
		if(i == 0)
		{
			add = infor[k][1];
			backtrack(k + 1, csum + add);
		}
		else if(i == 1)
		{
			add = 2 * infor[k][1];
			s0 += infor[k][0];
			backtrack(k + 1, csum + add);
			s0 -= infor[k][0];
		}
		else
		{
			int t2 = s2, t1 = s1, t0 = s0; 
			int total = infor[k][0];
			if(s0 + s1 + s2 >= total)
			{
				if(s2 >= total)
				{
					s2 = s1;
					s1 = s0;
					s0 = 0;
				}
				else if(s2 + s1 >= total)
				{
					s2 = s2 + s1 - total;
					s1 = s0;
					s0 = 0;

				}
				else
				{
					s1 = s2 + s1 + s0 - total;
					s2 = 0;
					s0 = 0;
				}
				backtrack(k + 1, csum);
				s2 = t2;
				s1 = t1;
				s0 = t0;
			}
		}
	}
}
int main()
{
	int tc;
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(tc = 1; tc <= T; ++tc)
	{
		cin>>N;
		for(int i = 0; i < N; i++)
		{
			cin>>infor[i][0]>>infor[i][1];
		}
		ans = INF; 
		s0 = s1 = s2 = 0;
		backtrack(0, 0);
		cout<<"#"<<tc<<" "<<ans<<endl;
	}
	return 0;
}