Traveling Salesperson Tour

There are N cities numbered from 1 to N. Some ordered pairs of cities can be traveled between, and some cannot. A salesperson wants to start from one city, visit every city exactly once, and then return to the starting city. Returning to the starting city at the very end is the only allowed revisit.

The travel costs are given as a matrix W. W[i][j] is the cost to move from city i to city j. Costs are directed, so W[i][j] does not have to equal W[j][i]. W[i][i] is always 0. If it is impossible to move from city i to city j, then W[i][j] is also 0.

Given N and the cost matrix W, find the minimum total cost among all valid tours.

The first line contains the number of cities N. (2 <= N <= 16)

Each of the next N lines contains one row of the cost matrix. Each entry is a positive integer not greater than 1,000,000 when the move is possible, and 0 when the move is impossible. W[i][j] is the cost to move from city i to city j.

Only inputs for which at least one valid tour exists are given.

Print the minimum cost required for the salesperson's tour on the first line.