Untitled

package OT;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoComeHome {
	static int n, arr[][], s0, s1, s2, min, ans;

	static void backtrack(int k, int csum) {
		int add;
		add = 0;
		if (csum >= min) {
			return;
		}
		if (k == n) {
			min = Math.min(min, csum);
			return;
		}
		for (int i = 0; i < 3; i++) {
			if (i == 0) {
				add = arr[k][1];
				backtrack(k + 1, csum + add);
			} else if (i == 1) {
				add = 2 * arr[k][1];
				s0 += arr[k][0];
				backtrack(k + 1, csum + add);
				s0 -= arr[k][0];
			} else {
				int t2 = s2, t1 = s1, t0 = s0;
				int total = arr[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;
				}
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Input.txt"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			n = scanner.nextInt();
			arr = new int[n][2];
			for (int i = 0; i < n; i++) {
				arr[i][0] = scanner.nextInt();
				arr[i][1] = scanner.nextInt();
			}

			min = Integer.MAX_VALUE;
			s0 = s1 = s2 = 0;
			backtrack(0, 0);
			System.out.println("#" + Case + " " + min);

		}
	}
}