Find the shortest path from the first vertex traversing all other vertices in a complete graph and returning back to the first vertex.

Input

Input begins with n (1 ≤ n ≤ 11) of number of vertexes of a graph. The following n lines to have the cost matrix of the graph with n non-negative integers (0 ≤ cost ≤ 100) in each line separated by spaces.

Output

Print the cost of the shortest circuit starting at the first vertex and traversing through all other vertices of the complete graph.

Example

Input:
5
0 100 125 100 75
100 0 50 75 125
125 50 0 100 125
100 75 100 0 50
75 125 125 50 0

Output:
375