Hugo Ve Nha

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

public class HugoVeNha {
    static int N;
    static int gate[][];
    static int res;
    static int armyAtGate[], expAtGate[];

    static void BT(int k, int cost){
        if(k == N){
            res = res < cost ? res : cost;
            return;
        }
        if(cost > res)
            return;

        //Pass
        BT(k+1, cost + gate[k][1]);

        //Hire
        armyAtGate[k] += gate[k][0];
        BT(k+1, cost + gate[k][1]*2);
        armyAtGate[k] -= gate[k][0];
        
        //Combat
        int total = 0;
        int tmp_army[] = new int[21];
        int tmp_exp[] = new int[21];
        for(int i = 0; i < k; i++){
            tmp_army[i] = armyAtGate[i];
            tmp_exp[i] = expAtGate[i];

            if(armyAtGate[i] > 0 && expAtGate[i] < 3){
                total += armyAtGate[i];
            }
        }

        int enermy = gate[k][0];
        if(total < enermy)
            return;

        for(int i = 0; i < k; i++){
            if(armyAtGate[i] <= 0 || expAtGate[i] >= 3)
                continue;
            int tmp_enermy = enermy;
            enermy -= armyAtGate[i];
            armyAtGate[i] -= tmp_enermy;    
            if(enermy <= 0)
            break;
        }

        for(int i = 0; i < k; i++){
            if(armyAtGate[i] > 0 || expAtGate[i] < 3)
                expAtGate[i] += 1;
        }
        
        BT(k+1, cost);

        for(int i = 0; i < k; i++){
            armyAtGate[i] = tmp_army[i];
            expAtGate[i] = tmp_exp[i];
        }
    }

    public static void main(String[] args) {
        try {
            System.setIn(new FileInputStream("input_HugoVeNha.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for(int t = 1; t <= T; t++){
            N = sc.nextInt();
            gate = new int[21][2];
            for(int i = 0; i < N; i++){
                gate[i][0] = sc.nextInt();
                gate[i][1] = sc.nextInt();
            }

        //Solve
        res = 999999;
        armyAtGate = new int[21];
        expAtGate = new int[21];
        BT(0, 0);

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