Traveling Salesman Problem: Minimum Cycle Distance

You are given a complete weighted graph representing n cities. The distance between city i and city j is given by a matrix \(D\) where \(D_{ij}\) represents the distance from city i to city j. Mr. Smith wants to start from city 0, visit every other city exactly once and then return back to city 0. Your task is to determine the minimum total distance he must travel.

Mathematical Formulation:

Let \(P = [0, p_1, p_2, \ldots, p_{n-1}, 0]\) be a permutation of the cities with the starting city fixed at 0. You need to minimize the cost:

\[ \text{Cost}(P) = D_{0,p_1} + \sum_{i=1}^{n-2} D_{p_i,p_{i+1}} + D_{p_{n-1},0} \]

Find the minimum \(\text{Cost}(P)\).

inputFormat

The input is given from stdin in the following format:

n
D0,0 D0,1 ... D0,n-1
D1,0 D1,1 ... D1,n-1
... 
Dn-1,0 Dn-1,1 ... Dn-1,n-1

Where the first line contains an integer n (the number of cities), and the following n lines each contain n space-separated integers representing the distance matrix \(D\).

outputFormat

Output a single integer to stdout representing the minimum total traveling distance required for Mr. Smith's trip.

## sample

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80