Travel Cost Optimization in a League

In a round-robin league tournament, every pair of teams plays two matches: one at each team’s home. Given an integer (n) which denotes the number of teams and a symmetric (n \times n) cost matrix (d) (with (d[i][i]=0)) where (d[i][j]) represents the travel cost from team (i) to team (j), the total travel cost for the tournament is defined as:

[ \text{Total Cost} = 2 \sum_{0 \le i < j < n} d[i][j] ]

Your task is to compute the minimum total travel cost required to conduct the tournament. Each match contributes twice the corresponding travel cost since teams travel to each other’s venues.

inputFormat

The input is read from standard input (stdin) with the following format:

• The first line contains a single integer (n) representing the number of teams.
• The following (n) lines each contain (n) space-separated integers, where the (j)-th integer on the (i)-th line represents (d[i][j]), the travel cost from team (i) to team (j).

It is guaranteed that (d[i][j] = d[j][i]) for all (0 \le i, j < n) and that (d[i][i] = 0).

outputFormat

Output a single integer which is the minimum total travel cost required to complete the tournament. The result should be printed to standard output (stdout).## sample

3
0 10 15
10 0 20
15 20 0

90