Minimum Value Cycle Partition

You are given an undirected complete graph with n vertices (where n is odd) and weighted edges. A cycle edge group of size k is defined as an array of edges \( [e_1,e_2,\dots,e_k] \) satisfying:

• \( k>1 \).
• For every \( i\in\{1,2,\dots,k\} \), the edge \( e_i \) shares exactly one common endpoint with each of \( e_{i-1} \) and \( e_{i+1} \) (with the cyclic convention \( e_0=e_k \) and \( e_{k+1}=e_1 \)).

Thus the edges in a cycle edge group form a cycle in the graph.

Define the function \( f(e_1,e_2) \) for any two edges as the maximum of their weights, i.e. \( f(e_1,e_2)=\max\{w(e_1),w(e_2)\} \).

The value of a cycle edge group \( C=[e_1,e_2,\dots,e_k] \) is defined as \[ V(C)=\sum_{i=1}^{k} f(e_i,e_{i+1})\quad (\text{with }e_{k+1}=e_1). \]

A cycle partition of the graph is a collection of disjoint cycle edge groups whose union is the entire set of edges of the graph. The value of a cycle partition is the sum of the values of its cycle edge groups.

Your task is to find the cycle partition with the minimum possible value and output that value.

Hint: It can be shown that any cycle partition corresponds to a pairing for the edges incident to each vertex. For every vertex, if you sort the weights on the incident edges and pair them consecutively, the sum of the maxima in each pair yields the minimum cost contribution for that vertex. The overall answer is the sum over all vertices.

inputFormat

The first line contains an odd integer n (the number of vertices). The following n lines each contain n integers. The j-th integer in the i-th line represents the weight of the edge between vertex i and vertex j. It is guaranteed that the graph is complete, i.e. the weight matrix is symmetric and the diagonal elements are 0.

outputFormat

Output a single integer, which is the minimum possible value of a cycle partition.

sample

3
0 1 3
1 0 2
3 2 0

8