Problem K
Traveling Salesman

To solve this problem, you will need to compute the total weight of the lightest Hamiltonian cycle in a complete, directed graph.

For example, consider the graph in Figure 1.

The lightest Hamiltonian cycle goes from vertex 0 to vertex 1 to vertex 2 and then back to vertex 0, with a total weight of 9.

Input

The first line contains $n$, where $2 \le n \le 50$.

Each of the next $n$ lines contains $n$ integers, each of which is between 1 and 500, inclusive. This $n$ by $n$ grid of integers is the adjacency matrix for an $n$-vertex complete, directed graph.

Output

Produce a single line of input that contains the total weight of the lightest Hamiltonian cycle contained in the graph described in the input.

2
1 3
2 1

5

3
1 2 7
6 5 4
3 8 9

9