Yulia works for a metal processing plant in E\(ka- te\)rinburg. 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- pr\)ocessed ore. Yulia needs to partition these sh\(ip- me\)nts into two groups based on their similarity. Then, each group is sent to one of two ore p\(ro- ce\)ssing buildings of the plant. To perform this partitioning, Yulia first calculates a numeric distance \(d\)(i, j) for each pair of sh\(ip- me\)nts \(1 \le i \le n\) and \(1 \le j \le n\), where the smaller the distance, the more similar the sh\(ip- me\)nts \(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 {i,j} }_{S^{d}}^{i, j^{)} Yulia then partitions the shipments into two subsets \(A\) and \(B\) in such a way that the sum of their disp\(ar- it\)ies \(D\)(\(A\)) + \(D\)(\(B\)) is minimized. Your task is to help her find this partitioning.

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).

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

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2014