당신은 N개의 도시를 최소비용으로 한 번씩 방문하려고 한다. 하지만 가장 효율적인 경로를 구하는 것은 매우 어려운 일이다. 따라서 당신은 다음과 같은 제약조건을 덧붙이기로 했다.

조건) K번 도시를 방문하기 전에 1~K-1번 도시를 모두 방문하거나 K번 도시를 방문한 후에 1~K-1번 도시를 모두 방문해야 한다.

각 도시 간 통행비용이 주어질 때 모든 도시를 방문하기 위한 최소비용을 구하여라. 출발 도시와 도착 도시는 마음대로 정할 수 있다.

입력 형식

• 첫 번째 줄에는 도시의 수 N이 주어진다. (1 ≤ N ≤ 1,500)
• 두 번째 줄부터 N개의 줄에는 아래 형식에 맞게 수들이 주어진다.
  - A+1번째 줄의 B번째 수는 도시 A에서 도시 B까지 갈 때 드는 비용이다.

전체 데이터의 1/3은 N ≤ 10이며, 전체 데이터의 1/2는 N ≤ 20이다.

출력 형식

입출력 예

입력 예 1
출력 예 1
3
0 5 2
5 0 4
2 4 0
7
입력 예 2
출력 예 2
4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0
31


입력 예 1 설명
2-1-3 또는 3-1-2의 경로로 도시를 방문한다면 7의 비용이 든다. 1-3-2의 경로로 도시를 방문한다면 6의 비용이 들지만 조건을 만족하지 않는다.

The travelling salesman is on a mission to visit N cities, each exactly once. The cities are represented by numbers 1, 2, ..., 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 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 ≤ N ≤ 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

SAMPLE TESTS

input 
 
3 
0 5 2 
5 0 4 
2 4 0 
 
output 
 
7 

input 
 
4 
0 15 7 8 
15 0 16 9 
7 16 0 12 
8 9 12 0 
 
output 
 
31 
Clarification of the first example: the optimal sequence is 2, 1, 3 or 3, 1, 2. The sequence 1, 3, 2 is 
even more favourable, but it does not fulfill the salesman's condition. 
Clarification of the second example: the sequence is either 3, 1, 2, 4 or 4, 2, 1, 3.

출처:coci/2013-2014/contest2 4번