Toll_gate_Samsung

/*
TESTED AND VERIFIED
INPUT:-
3
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
11
1000 10
700 900
400 500
300 10
900 900
300 10
50 900
50 900
700 900
500 900
50 10

OUTPUT>-
150
3300
2370

*/

#include<iostream>

using namespace std;

struct p{
    int cost,men;
}toll[100];

int n;
int ans;

void solve(int cur_toll, int bt1,int bt2, int bt3, int cost ){
    //optimization
    if(cost > ans)return;

    //base case when we have covered all toll booths
    if(cur_toll==n){
        ans=min(ans,cost);
        return;
    }

    //paying the toll
    solve(cur_toll + 1, bt1, bt2, bt3, cost + toll[cur_toll].cost);
    //buying the men at the toll by paying double cost
    solve(cur_toll + 1, bt1, bt2, bt3 + toll[cur_toll].men, cost + 2*toll[cur_toll].cost);

    //total men available for fighting
    int total_men= bt1 + bt2 + bt3;

    //fighting the men at toll to not pay the toll tax
    if(total_men > toll[cur_toll].men){
        if( toll[cur_toll].men > bt1 + bt2) bt3 = total_men - toll[cur_toll].men;
        if(toll[cur_toll].men > bt1) bt2= (toll[cur_toll].men >= bt1 +bt2) ? 0 : bt2 - toll[cur_toll].men + bt1;
        solve(cur_toll + 1, bt2, bt3, 0, cost);
    }
}


int main(){
    int t;
    cin>>t;
    while(t--){
        //no of tolles
        cin>>n;

        for(int i=0; i<n; i++)
            cin>>toll[i].men>>toll[i].cost;

        ans=999999;
        solve(0,0,0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}