Minimum Flight Time with Two‐End Insertion

Salesman Sept has a task to visit (N) cities (numbered from (1) to (N)), each exactly once. Every pair of cities is connected by a flight with a given travel time. Sept wants to minimize the total flight time by choosing a proper order to visit all cities. However, he has a strange requirement on the visiting order:

• There is no restriction for city (1).
• For any city (K) with (2 \le K \le N), all cities with numbers less than (K) must be visited either entirely before city (K) or entirely after city (K). In other words, for any two cities (X,Y) with (1 \le X,Y < K), it cannot happen that (X) is visited before (K) while (Y) is visited after (K).

It can be shown that the above condition is equivalent to constructing the visiting order by starting with city (1) and then, for each city from (2) to (N), inserting the new city either at the beginning or at the end of the current route.

Given the flight times between every pair of cities, compute the minimum total flight time along the route. The flight time along a route is defined as the sum of the flight times between consecutive cities in the chosen order.

The flight time from city (i) to city (j) is denoted by (T_{ij}) (in (\LaTeX) format: (T_{ij})).

inputFormat

The first line contains an integer \(N\) \((2 \le N)\), the number of cities.

Then follow \(N\) lines, each containing \(N\) space-separated integers. The \(j\)-th integer in the \(i\)-th line represents the flight time \(T_{ij}\) from city \(i\) to city \(j\). It is guaranteed that the values are non-negative and that \(T_{ij}\) is given for every pair of distinct cities.

outputFormat

Output a single integer, the minimum total flight time that Sept can achieve while satisfying the visiting order requirement.

sample

3
0 1 3
1 0 2
3 2 0

3