You're given a complete, directed, weighted graph with N vertices. Find the length of the shortest possible route visiting all the vertices exactly once, and returns to the original vertex.

Input

The first line of input contains an integer N, the number of vertices. (N ≤ 18)

The rest of the input contains the (NxN) adjacency matrix of the graph.

The (i + 1)-th row, j-th column of the input contains the weight w(i, j) of the directed edge (i, j). (0 ≤ w(i, j) ≤ 1000000, w(i, i) = 0)

Output

To the first and only line of output print the desired length.

Example

Input:
3
0 1 2
2 0 1
2 2 0
3
0 1 2
2 0 1
2 2 0


Output:
4