Traveling Salesperson Problem

You are given n attractions and a symmetric distance matrix \(D\) of size \(n \times n\), where \(D[i][j]\) represents the distance between the \(i^{th}\) and \(j^{th}\) attraction. Your task is to compute the length of the shortest possible route that starts from one attraction, visits each of the other attractions exactly once, and returns to the starting point.

This is a classic example of the Traveling Salesperson Problem (TSP). Formally, if \(\pi\) is a permutation of \(\{0, 1, \dots, n-1\}\), you need to minimize:

[ \min_{\pi} \left( D[\pi(0)][\pi(1)] + D[\pi(1)][\pi(2)] + \cdots + D[\pi(n-2)][\pi(n-1)] + D[\pi(n-1)][\pi(0)] \right) ]

Note that the distance from an attraction to itself is 0, i.e., \(D[i][i] = 0\), and the matrix is symmetric: \(D[i][j] = D[j][i]\).

inputFormat

The input is given via standard input and has the following format:

n
row_1
row_2
... 
row_n

Where:

• n (an integer) represents the number of attractions.
• Each of the next n lines contains n space-separated integers. The \(j^{th}\) integer of the \(i^{th}\) line represents the distance between attraction \(i\) and attraction \(j\).

outputFormat

Output a single integer which is the length of the shortest route that visits every attraction exactly once and returns to the starting point. The output should be written to standard output.

## sample

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

80