Untitled

public class Solution {
	static int T, g;
	static int gate[][], min;
	static int sg[], count[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			g = sc.nextInt();
			gate = new int[g][2];
			for (int i = 0; i < g; i++) {
				gate[i][0] = sc.nextInt(); 
				gate[i][1] = sc.nextInt(); 
			}

			min = 123456789;
			sg = new int[g];
			count = new int[g];
			backTrack(0, 0);
			System.out.println("#" + tc + " " + min);
		}
	}

	public static void backTrack(int k, int sum) {
		if (sum >= min)
			return;
		if (k == g) {
			if (sum < min)
				min = sum;
			return;
		}
		backTrack(k + 1, sum + gate[k][1]);
		sg[k] += gate[k][0];
		backTrack(k + 1, sum + 2 * gate[k][1]);
		sg[k] -= gate[k][0];
		int number = 0;
		int tc[] = new int[21];
		int ts[] = new int[21];
		for (int i = 0; i < k; i++) {

			tc[i] = count[i];
			ts[i] = sg[i];
			if (tc[i] < 3 && ts[i] > 0)
				number += sg[i];
		}
		if (number < gate[k][0])
			return;
		int ss = gate[k][0];
		for (int i = 0; i < k; i++) {
			if (count[i] >= 3 || sg[i] <= 0)
				continue;
			int m = ss;
			ss -= sg[i];
			sg[i] -= m;

			if (ss <= 0)
				break;
		}
		for (int i = 0; i < k; i++) {
			if (count[i] < 3 && sg[i] > 0)
				count[i]++;
		}
		backTrack(k + 1, sum);
		for (int i = 0; i < k; i++) {
			count[i] = tc[i];
			sg[i] = ts[i];
		}
	}
}