Description

In a certain township, there are $n$ villages. A salesman needs to visit each village to sell goods. The distances $s_{i,j}$ between villages are known, and, in general, the road from village A to village B may be different from the road from village B to village A. To improve efficiency, he starts from the store, visits each village exactly once, and then returns to the village where the store is located. Assume the store is in village $1$. He does not know which route will minimize the total distance traveled. Please help him choose a route with the shortest total length.

Input Format

The first line contains an integer $n$, the number of villages.
The next $n$ lines each contain $n$ integers. In the $i$-th line, the $j$-th integer represents the distance $s_{i,j}$ of the one-way path from $i$ to $j$.

Output Format

Output a single integer on one line, representing the length of the shortest route.

3
0 2 1
1 0 2
2 1 0

3

Hint

For all testdata, it is guaranteed that $2 \leq n \leq 20$, $1 \leq s_{i,j} < 10^3$.

Translated by ChatGPT 5