Untitled

#include <iostream>

using namespace std;

int T, N;
int sol[25];
int price[25];
int ans;
int minA;
int num;
int sol0, sol1, sol2;


void backtrack(int k){
	if(k == N){
		if(ans < minA){
			minA = ans;
		}
		return;
	}
	if(ans >= minA){
		return;
	}

	for(int i = 0; i < 3; i++){
		if(i == 0){
			ans += price[k];
			backtrack(k + 1);
			ans -= price[k];
		}
		if(i == 1){
			ans += price[k] * 2;
			sol0 += sol[k];
			backtrack(k + 1);
			ans -= price[k] * 2;
			sol0 -= sol[k];
		}
		if(i == 2){
			if(sol0 + sol1 + sol2 >= sol[k]){
				int s1 = sol0;
				int s2 = sol1;
				int s3 = sol2;

				if(sol2 >= sol[k]){
					sol2 = sol1;
					sol1 = sol0;
					sol0 = 0;
				}else if(sol2 + sol1 >= sol[k]){
					sol2 = sol2 + sol1 - sol[k];
					sol1 = sol0;
					sol0 = 0;
				}else if(sol2 + sol1 + sol0 >= sol[k]){
					sol1 = sol2 + sol1 + sol0 - sol[k];
					sol2 = 0;
					sol0 = 0;
				}
				backtrack(k + 1);

				sol0 = s1;
				sol1 = s2;
				sol2 = s3;
			}
		}
	}
}

int main(){
	freopen("input.txt" ,"rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N;
		for(int i = 0; i < N; i++){
			cin >> sol[i] >> price[i];
		}
		minA = 1000000;
		ans = 0;
		num = 0;
		sol1 = sol2 = sol0 = 0;
		backtrack(0);
		cout << "#" << tc << " " << minA << endl;
	}
	return 0;
}