# Putnik

Chances are that you have probably already heard of the travelling salesman problem. If you have, then you are aware that it is an NP-hard problem because it lacks an efficient solution. Well, this task is an uncommon version of the famous problem! Its uncommonness derives from the fact that this version is, actually, solvable.

The travelling salesman is on a mission to visit $N$ cities, each exactly once. The cities are represented by numbers $1, 2, \ldots , N$. What we know is the direct flight duration between each pair of cities. The salesman, being the efficient man that he is, wants to modify the city visiting sequence so that the total flight duration is the minimum possible.

Alas, all is not so simple. In addition, the salesman has a
peculiar condition regarding the sequence. For *each*
city labeled $K$ the
following must apply: either all cities with labels smaller
than $K$ have been visited
before the city labeled $K$ or they will all be visited after
the city labeled $K$. In
other words, the situation when one of such cities is visited
before, and the other after is not allowed.

Assist the poor fellow in his ambitious mission and calculate the minimum total flight duration needed in order to travel to all the cities, starting from whichever and ending in whichever city, visiting every city exactly once, so that his peculiar request is fulfilled.

## Input

The first line of input contains the positive integer $N$ ($2 \leq N \leq 1500$), the number of cities. Each of the following $N$ lines contains $N$ positive integers from the interval $[0,\, 1000]$. The number in $B$-th place in the $A$-th row represents the flight duration between cities $A$ and $B$; that number is equal to the $A$-th number in the $B$-th row. When $A = B$, that number is 0. Otherwise, it is a positive value.

## Output

The first and only line of output must contain the required minimum total flight duration.

Sample Input 1 | Sample Output 1 |
---|---|

3 0 5 2 5 0 4 2 4 0 |
7 |

Sample Input 2 | Sample Output 2 |
---|---|

4 0 15 7 8 15 0 16 9 7 16 0 12 8 9 12 0 |
31 |