Shortest Hike Path

You are given n points of interest along with a complete matrix of distances between every pair of points. Your task is to compute the minimum total distance of a tour that starts at a point, visits each of the other points exactly once, and finally returns to the starting point. Formally, you need to minimize the expression $$\min_{\pi \in S_n} \sum_{i=0}^{n-1} d(\pi_i, \pi_{(i+1) \bmod n})$$, where \(d(i,j)\) represents the distance from point \(i\) to point \(j\). This problem is a variant of the Traveling Salesman Problem.

inputFormat

The input is read from standard input. The first line contains an integer n representing the number of points. Each of the next n lines contains n space-separated integers. The j-th integer on the i-th line represents the distance from point i to point j.

outputFormat

Output a single integer, the total distance of the shortest round-trip path.## sample

3
0 29 20
29 0 15
20 15 0

64