Description

Salesman Sept has a task: to visit $N$ cities (numbered from $1$ to $N$), and each city must be visited exactly once.

Among these $N$ cities, there is a flight between every pair of cities. Sept values efficiency, so he wants to minimize the total time spent flying. For this, he may change the visiting order of the cities.

However, Sept has a strange requirement for the visiting order:

• There is no requirement for city $1$.
• If he is going to visit city $K(K\in[2,N])$, then all cities with numbers smaller than $K$ must be visited either all before visiting city $K$, or all after visiting city $K$.
  In other words, for two cities $X,Y(1\le X,Y< K)$, it is not allowed that city $X$ is visited before city $K$ while city $Y$ is visited after city $K$.

Under these restrictions, given the time needed to take flights between every pair of cities, find the minimum total flying time Sept spends.

Input Format

The first line contains an integer $N$, the number of cities.

The next $N$ lines each contain $N$ integers. Let $(A,B)$ denote the $B$-th number in the $A$-th line. Then:

• $(A,B)$ is the time needed to take a flight between cities $A$ and $B$.
• If $A=B$, then $(A,B)=0$.
• $(A,B)=(B,A)$.

Output Format

Output one integer in a single line, the minimum total flying time Sept spends.

3 
0 5 2 
5 0 4 
2 4 0

7

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

31

Hint

Explanation of Sample 1

The order $\tt2,1,3$ or $\tt3,1,2$ is valid.

Note that $\tt1,3,2$ takes less time, but it does not satisfy Sept's strange requirement.

Explanation of Sample 2

The order $\tt3,1,2,4$ or $\tt4,2,1,3$ is valid.

Constraints

This problem does not use bundled testdata, and subtasks will not be shown in judging.

• Subtask 1 $\tt(40pts)$: $2\le N\le 10$.
• Subtask 2 $\tt(20pts)$: $2\le N\le 20$.
• Subtask 3 $\tt(60pts)$: no special restrictions.

For $100\%$ of the data, $2\le N\le 1500$, $0\le (A,B)\le 10^3$.

Source

This problem is translated from COCI2013-2014 CONTEST 2 T4 PUTNIK.

According to the original testdata setup, the full score of this problem is $120$ points.

Translated by ChatGPT 5