# Untitled

unknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
```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();
}
}
```