1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class kug {

	private static final String SEPARATOR = "\\s+";
	public static InputStream inputStream = System.in;

	public static long[][] cloneArrayWithoutRow(long[][] src, int row) {
		int length = src.length;
		long[][] target = new long[length - 1][];

		for (int i = 0; i < row; i++) {
			target[i] = new long[length - i - 1];
			System.arraycopy(src[i], 0, target[i], 0, row - i);

			System.arraycopy(src[i], row - i + 1, target[i], row - i, length - 1 - row);
		}

		for (int i = row + 1; i < length; i++) {
			target[i - 1] = new long[length - i];

			System.arraycopy(src[i], 0, target[i - 1], 0, src[i].length);
		}

		updateValues(src, target, row);

		return target;
	}

	private static void updateValues(long[][] src, long[][] target, int row) {

		if (row != target.length) { // not last row
			for (int i = 0; i < target.length - row; i++) {
				target[row][i] = Math.min(target[row][i], src[row][i + 1]);
			}
		}

		for (int i = 0; i < row; i++) {

			target[i][row - i - 1] = Math.min(target[i][row - i - 1], src[i][row - i]);
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(inputStream));

		int bucketsNumber = Integer.parseInt(br.readLine());

		long[][] data = new long[bucketsNumber][];

		for (int i = 0; i < bucketsNumber; i++) {
			int size = bucketsNumber - i;

			data[i] = new long[size];

			String[] tmp = br.readLine().split(SEPARATOR);

			for (int j = 0; j < size; j++) {
				data[i][j] = Long.valueOf(tmp[j]);
			}
		}

		solve(data, 0L);

		System.out.println(globalMin);

	}

	private static final int FIRST_COLUMN = 0;
	private static final int FIRST_ROW = FIRST_COLUMN;

	private static long globalMin = Long.MAX_VALUE;

	private static void solve(long[][] data, long min) {
		if (min >= globalMin) {
			return;
		}

		if (data.length == 1) {
			if (min + data[FIRST_ROW][FIRST_COLUMN] < globalMin) {
				globalMin = min + data[FIRST_ROW][FIRST_COLUMN];
				return;
			}

		}

		for (int i = 0; i < data.length; i++) {
			solve(cloneArrayWithoutRow(data, i), min + data[i][FIRST_COLUMN]);
		}

	}

}