Traveling Salesperson Problem

You are given a complete graph with n cities and an n × n cost matrix, where the element at the i-th row and j-th column represents the travel cost from city i to city j. The task is to determine the minimum travel cost for a salesperson who starts at city 0, visits every city exactly once, and returns to city 0.

You are advised to use dynamic programming with bitmasking. The recurrence used in the solution can be stated in LaTeX format as:

$$ \text{dp}[mask][j] = \min_{i \notin mask}\{ \text{dp}[mask \setminus \{j\}][i] + cost[i][j] \} $$

If mask represents the set of visited cities (as a bitmask), then when mask = (1 \ll n) - 1 (i.e. all cities have been visited), the cost to return to the origin city is added.

inputFormat

The first line of the input contains a single integer n representing the number of cities. The following n lines each contain n space-separated integers representing the cost matrix.

For example:

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

outputFormat

Output a single integer which is the minimum travel cost for the route starting and ending at city 0 while visiting all cities exactly once.

## sample

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

80

</p>