Untitled

package hugo_ve_nha;

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

public class Solution {
	static int n, res;
	static int[] bsi, price, used, a;

	public static void backTrack(int k, int count) {
		if (count >= res) {
			return;
		}
		if (k == n) {
			res = Math.min(res, count);
			return;
		}
		// pass
		backTrack(k + 1, count + price[k]);

		// hire
		a[k] = bsi[k];
		backTrack(k + 1, count + 2 * price[k]);
		a[k] = 0;
		
		//battle
		int binh = 0;
		for(int i = 0; i < n; i++){
			if(used[i] < 3){
				binh += a[i];
			}
		}
		if(binh >= bsi[k]){
			int[] st = new int[n], stl = new int[n];
			for(int i = 0; i < n; i++){
				st[i] = used[i];
				stl[i] = a[i];
			}
			for(int i = 0; i < n; i++){
				if(a[i] > 0){
					used[i] ++;
				}
			}
			int dich = bsi[k];
			for(int i = 0; i < n; i++){
				if(a[i] > 0 && used[i] < 4){
					if(dich >= a[i]){
						dich -= a[i];
						a[i] = 0;
					}else{
						a[i] -= dich;
						dich = 0;
					}
					
				}
			}
			backTrack(k+1, count);
			for(int i = 0; i < n; i++){
				used[i] = st[i];
				a[i] = stl[i];
			}
		}
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			bsi = new int[n];
			price = new int[n];
			used = new int[n];
			a = new int[n];
			for (int i = 0; i < n; i++) {
				bsi[i] = scanner.nextInt();
				price[i] = scanner.nextInt();
			}
			res = Integer.MAX_VALUE;
			
			backTrack(0, 0);

			System.out.println("#" + t + " " + res);
		}
		scanner.close();
	}
}