# Untitled

unknown
plain_text
13 days ago
1.4 kB
3
Indexable
Never
```import java.util.Scanner;

public class Solution {
static int n, arr[][], s0, s1, s2, min, ans;

static void backtrack(int k, int csum) {
if (csum >= min) {
return;
}
if (k == n) {
min = Math.min(min, csum);
return;
}
for (int i = 0; i < 3; i++) {
if (i == 0) {
backtrack(k + 1, csum + add);
} else if (i == 1) {
s0 += arr[k][0];
backtrack(k + 1, csum + add);
s0 -= arr[k][0];
} else {
int t2 = s2, t1 = s1, t0 = s0;
int total = arr[k][0];
if (s0 + s1 + s2 >= total) {
if (s2 >= total) {
s2 = s1;
s1 = s0;
s0 = 0;
} else if (s2 + s1 >= total) {
s2 = s2 + s1 - total;
s1 = s0;
s0 = 0;
} else {
s1 = s2 + s1 + s0 - total;
s2 = 0;
s0 = 0;
}
backtrack(k + 1, csum);
s2 = t2;
s1 = t1;
s0 = t0;
}
}
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
int tc = scanner.nextInt();
for (int Case = 1; Case <= tc; Case++) {
n = scanner.nextInt();
arr = new int[n][2];
for (int i = 0; i < n; i++) {
arr[i][0] = scanner.nextInt();
arr[i][1] = scanner.nextInt();
}

min = Integer.MAX_VALUE;
s0 = s1 = s2 = 0;
backtrack(0, 0);
System.out.println("#" + Case + " " + min);

}
}
}
```