Traveling Salesman Tour 2

Time limit2sMemory limit256 MB

Summary

Find the cheapest tour that starts at one city, visits each of N cities exactly once, and returns to the start using the given directed costs.

Level: Medium5 of 10
Topics: Dynamic programming, Bit manipulation, Graph
Solved: No attempts yet

Problem

The traveling salesman problem, TSP for short, is one of the most important problems in computer science. Several variants of it exist. This task uses the most common form.

Cities are numbered 1 through $N$ , and roads run between cities. Some pairs of cities have no road. A salesman wants to plan a tour that starts at one city, passes through all $N$ cities, and returns to the city he started from. He may not go back to a city he has already visited. Returning to the starting city at the very end is the only exception. Many such tours exist, and he wants the plan with the smallest total cost.

The cost of moving between cities is given as a matrix $W$ . $W[i][j]$ is the cost of going from city $i$ to city $j$ . The costs are not symmetric, so $W[i][j]$ may differ from $W[j][i]$ . Every travel cost is a positive integer, and $W[i][i]$ is always 0. There are cases where city $j$ cannot be reached from city $i$ , and such a case is written as $W[i][j] = 0$ .

Given $N$ and the cost matrix, write a program that finds the minimum cost of the salesman's tour.

Input

The first line contains the number of cities $N$ . ( $2 \le N \le 10$ ) Each of the next $N$ lines contains $N$ entries of the cost matrix. Each entry is a positive integer no greater than 1,000,000, and 0 is given when the move is impossible. $W[i][j]$ is the cost of going from city $i$ to city $j$ .

Every input allows at least one tour.

Output

Print the minimum cost of the salesman's tour on the first line.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
2
0 1
1 0
```
Expected output
```
2
```
Example 3
Input
```
2
0 1000000
1000000 0
```
Expected output
```
2000000
```
Example 4
Input
```
3
0 1 100
100 0 1
1 100 0
```
Expected output
```
3
```
Example 5
Input
```
3
0 4 0
0 0 5
6 0 0
```
Expected output
```
15
```