시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 (추가 시간 없음) 512 MB 1 1 1 100.000%

문제

KM city has N sightseeing areas. Currently every pair of area is connected by a bidirectional road.

However for some reason, Mr. KM, the mayor of this city, decided to make all of these roads one-way . It costs Ci,j dollars to renovate the road between area i and area j to a one-way road from area i to area j. Of course, Mr. KM is economic and wants to minimize the total cost of the renovation.

On the other hand, because tourism is the most important industry for KM city, there must exists a tour that goes through all the sightseeing areas, visiting each area exactly once. The first and last area of the path need not to be the same. Can you calculate the minimum total cost required for the renovation, given this situation?

입력

The first line contains the number of sightseeing area N (1 ≤ N ≤ 100). Next N lines describe the integer matrix C, where the j-th element of the i-th row of the input describes Ci,j (0 ≤ Ci,j ≤ 1, 000, 000). For each i, you can assume Ci,i is always zero.

출력

Output the minimum cost in a line.

예제 입력 1

3
0 2 7
2 0 4
5 8 0

예제 출력 1

11