ICPC 2014 · Problem G · Metal Processing Plant

Time Limit: 4 seconds

Picture from Wikimedia Commons Yulia works for a metal processing plant in Eka- terinburg. This plant processes ores mined in the Ural mountains, extracting precious metals such as chalcopyrite, platinum and gold from the ores. Every month the plant receives $n$ shipments of un- processed ore. Yulia needs to partition these ship- ments into two groups based on their similarity. Then, each group is sent to one of two ore pro- cessing buildings of the plant.

To perform this partitioning, Yulia first calculates a numeric distance $d(i, j)$ for each pair of ship- ments $1 \le i \le n$ and $1 \le j \le n$, where the smaller the distance, the more similar the ship- ments $i$ and $j$ are. For a subset $S \subseteq \{1, . . . , n\}$ of shipments, she then defines the disparity $D$ of $S$ as the maximum distance between a pair of shipments in the subset, that is,

$D(S) = max$ $i,j\in S d(i, j).$

Yulia then partitions the shipments into two subsets $A$ and $B$ in such a way that the sum of their dispar- ities $D(A) +D(B)$ is minimized. Your task is to help her find this partitioning.

Input

The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 200$) indicating the number of shipments. The following $n- 1$ lines contain the distances $d(i, j)$. The $i^{th}$ of these lines contains $n- i$ integers and the $j^{th}$ integer of that line gives the value of $d(i, i+j)$. The distances are symmetric, so $d(j, i) = d(i, j)$, and the distance of a shipment to itself is $0$. All distances are integers between $0$ and $10^{9}$ (inclusive).

Output

Display the minimum possible sum of disparities for partitioning the shipments into two groups.

Sample Input 1

5
4 5 0 2
1 3 7
2 0
4

Sample Output 1

4

ACM-ICPC World Finals 2014 Problem G: Metal Processing Plant

Sample Input 2

7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3

Sample Output 2

15

ACM-ICPC World Finals 2014 Problem G: Metal Processing Plant