Untitled

package OnLan2;

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

public class hugovenha {
	static int N, gate[][], ans, binhsi, binhSiThamChien[];

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("hugovenha"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 0; tc < T; tc++) {
			N = sc.nextInt();
			gate = new int[2][N];
			for (int i = 0; i < N; i++) {
				gate[0][i] = sc.nextInt();// binh
				gate[1][i] = sc.nextInt();// chi phi

			}
			ans = Integer.MAX_VALUE;
			binhSiThamChien = new int[3];
//			binhsi = 0;
			backtrack(0, 0);
			System.out.println("#" + (tc + 1) + " " + ans);
		}
	}

	public static void backtrack(int gateIndex, int cost) {
		if (gateIndex == N) {
			ans = Math.min(ans, cost);
			return;
		}
		if (cost >= ans)//
			return;
		// Pass
		backtrack(gateIndex + 1, cost + gate[1][gateIndex]);

		// hire
		binhsi += gate[0][gateIndex];
		binhSiThamChien[0] += gate[0][gateIndex];
		backtrack(gateIndex + 1, cost + 2 * gate[1][gateIndex]);
		binhSiThamChien[0] -= gate[0][gateIndex];
		binhsi -= gate[0][gateIndex];

		// battle
		if (binhsi >= gate[0][gateIndex]) { //

			int old[] = setVisit(gateIndex);
			backtrack(gateIndex + 1, cost );//
			unSetvisit(old);
		}

	}

	public static int[] setVisit(int gateindex) {
		int old[] = new int[3];
		for (int i = 0; i < 3; i++) {
			old[i] = binhSiThamChien[i];
		}

		binhsi -= gate[0][gateindex];
		// cap nhat lại binh còn thuộc dạng đánh mấy lần
		int sum = 0;
		for (int i = 0; i < 3; i++) {
			if (sum + binhSiThamChien[i] > binhsi) {
				binhSiThamChien[i] = binhsi - sum;
				for (int j = i + 1; j < 3; j++) {
					binhSiThamChien[j] = 0;
				}
				break;//
			}
			sum += binhSiThamChien[i];
		}

		// sau khi danh nhau binh si se tang len 1 lan tham chien
		int leave = binhSiThamChien[2];
		binhsi -= leave;// update binh con
		for (int j = 2; j > 0; j--) {
			binhSiThamChien[j] = binhSiThamChien[j - 1];
		}
		binhSiThamChien[0] = 0;
		return old;
	}

	public static void unSetvisit(int old[]) {
		int sum = 0;
		for (int i = 0; i < 3; i++) {
			binhSiThamChien[i] = old[i];
			sum += old[i];
		}
		binhsi = sum;
	}

}