Problem G
                                   Metal Processing Plant
                                       Time Limit: 4 seconds
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 ≤ i ≤ n and 1 ≤ j ≤ n, where the                                              Picture from Wikimedia Commons

smaller the distance, the more similar the ship-
ments i and j are. For a subset S ⊆ {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 d(i, j).
                                                        i,j∈S

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 ≤ n ≤ 200) indicating
the number of shipments. The following n − 1 lines contain the distances d(i, j). The ith 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 109 (inclusive).

Output

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

 Sample Input 1                                            Sample Output 1
 5                                                         4
 4 5 0 2
 1 3 7
 2 0
 4

Sample Input 2                                Sample Output 2
7                                             15
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3