Shortest Tour

Statement

There are n cities numbered 1 to n and a table of travel distances: dist[i][j] is the cost of going directly from city i to city j. The distances need not be symmetric. Starting at city 1, visit every other city exactly once and then return to city 1. Find the smallest possible total distance of such a tour. With a single city the answer is 0.

Input

The first line has n. Each of the next n lines has n integers: row i of the distance table (dist[i][i] = 0).

Output

Print one integer: the length of the shortest tour.

Constraints

1 <= n <= 12
0 <= dist[i][j] <= 1000000, and dist[i][i] = 0

Example 1

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80

The tour 1, 2, 4, 3, 1 costs 10 + 25 + 30 + 15 = 80.

Example 2

2
0 7
9 0

16

Go to city 2 (7) and come back (9).