Untitled

package HugoVeNha;

import java.util.Scanner;

public class test {
static int N;
static int[][] Door=new int[100][2];
static int[] linh=new int[3];
static int ans=0;

static void backtrack(int k,int sum){
	if(k==N){
		if(sum<ans){
			ans=sum;
		}
		return;
	}
	if(sum>ans){
		return;
	}
	int Linh1=linh[0];
	int Linh2=linh[1];
	int Linh3=linh[2];
	for(int i=0;i<3;i++){
		if(i==0){
			backtrack(k+1, sum+Door[k][1]);
		}
		else if(i==1) {
			linh[0]+=Door[k][0];
			backtrack(k+1, sum+Door[k][1]*2);
			linh[0]=Linh1;
		}
		else {
			if(linh[0]+linh[1]+linh[2]>=Door[k][0]){
					int tmp = Door[k][0];
					for (int j = 2; j >= 0; j--) {
						if (tmp > linh[j]) {
							tmp -= linh[j];
							linh[j] = 0;
						} else {
							linh[j] -= tmp;
							break;
						}
					}
					linh[2] = linh[1];
					linh[1] = linh[0];
					linh[0] = 0;
					backtrack(k + 1, sum);
					linh[0]=Linh1;
					linh[1]=Linh2;
					linh[2]=Linh3;
			}
		}
	}
}
public static void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	int tc=scanner.nextInt();
	for(int i=0;i<tc;i++){
		N=scanner.nextInt();
		for(int j=0;j<N;j++){
			for(int k=0;k<2;k++){
				Door[j][k]=scanner.nextInt();
			}
		}
		ans=9999999;
		backtrack(0, 0);
		System.out.println("#"+(i+1)+" "+ans);
		
	}
}
}