Untitled

#include <iostream>
#define N 1001
#define oo 2000000
using namespace std;
int n,m;
int x[N];
int a[N],b[N];
int ans;
int linh[N*N];
int cong;
void doc()
{
	cin>>n;
	ans=oo;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	cong=0;
}

void backtrack(int u, int cp, int ar0, int ar1, int ar2)
{
	if(u==n+1)
	{
		//for(int i=1;i<=n;i++)cout<<x[i]<<" ";
		//cout<<"\n"<<cp<<"\n";
		if(cp<ans)ans=cp;
		return;
	}
	x[u]=0;
	if(cp+b[u]<ans)backtrack(u+1,cp+b[u],ar0,ar1,ar2);
	x[u]=1;
	if(cp+2*b[u]<ans)backtrack(u+1,cp+b[u]*2,ar0+a[u],ar1,ar2);
	
	if(ar0+ar1+ar2>=a[u])
	{
		int linh=a[u];
		linh-=ar2;
		if(linh<0)linh=0;
		int i,j,l;
		i=0;
		j=ar0;
		l=ar1;
		if(linh>l)
		{
			linh-=l;
			l=0;
			j-=linh;
			linh=0;

		}else l-=linh,linh=0;


		backtrack(u+1,cp,i,j,l);
		cong--;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		backtrack(1,0,0,0,0);
		cout<<"#"<<tc<<" "<<ans<<"\n";
	}
	return 0;
}