# Untitled

unknown
plain_text
a year ago
2.2 kB
3
Indexable
Never
```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;
}
}
}
```