Untitled

package HugoVeNha;

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

public class Solution {
    static int n,ans,front,rear;
    static int[] soldiers,costs,d;
    static int[][] a;
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("input.txt"));
        System.setOut(new PrintStream("output.txt"));
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int t=1;t<=tc;t++){
            n = sc.nextInt();
            costs = new int[n];
            soldiers = new int[n];
            d = new int[n];
            for(int i=0;i<n;i++){
                soldiers[i] = sc.nextInt();
                costs[i] = sc.nextInt();
            }
            a = new int[n][3];
            ans = Integer.MAX_VALUE;
            BT(0,0,0);
            System.out.println(ans);
        }
    }
    static void BT(int i,int total, int battle){
        if(i==n){
            // for(int j=0;j<n;j++){
            //     System.out.print(d[j]+" ");
            // }
            // System.out.println();
            ans = Math.min(ans, total);
            return;
        }
        if(total>=ans) return;
        //PASS
        d[i] = 1;
        BT(i+1,total+costs[i],battle);
        d[i] = 0;
        //HIRE
        d[i] = 2;
        a[battle][2]+=soldiers[i];
        BT(i+1,total+costs[i]*2,battle);
        a[battle][2]-=soldiers[i];
        d[i] = 0;
        //BATTLE
        if(a[battle][0]+a[battle][1]+a[battle][2]>=soldiers[i]){
            if(a[battle][0]<=soldiers[i]){
                if(a[battle][1]<=soldiers[i]-a[battle][0]){
                    a[battle+1][2] = a[battle+1][2] - (soldiers[i]-a[battle][0]-a[battle][1]);
                }
                else a[battle+1][1] = a[battle][1] - (soldiers[i]-a[battle][0]);
            }
            else a[battle+1][0] = a[battle][0] - soldiers[i];
            d[i] = 3;
            BT(i+1,total,battle+1);
            for(int j=0;j<3;j++){
                a[battle+1][j]=a[battle][j];
            }
            d[i] = 0;
        }
    }
}