Minimum Delivery Cost

You are given a depot and n cities (including the depot) along with a cost matrix representing the travel cost between any two cities. The depot is always considered as city 0. Your task is to calculate the minimum total cost required for trucks to deliver packages from the depot to each of the other cities and then return directly to the depot for each delivery.

For each city i (where i ranges from 1 to n-1), the round trip cost is given by:

\(2 \times cost_{0,i}\)

The overall minimum delivery cost is the sum of the individual round trip costs for all cities (except the depot). Formally, if the cost matrix is \(C\), the total cost is:

\(\text{Total Cost} = \sum_{i=1}^{n-1} 2 \times C_{0,i}\)

Note that the cost matrix is guaranteed to be symmetric with zero on the diagonal (i.e. \(C_{i,i} = 0\)).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 100), representing the number of cities including the depot.

The following n lines each contain n space-separated integers. The j-th integer in the i-th line represents the cost \(C_{i,j}\) for traveling from city i to city j. It is guaranteed that \(C_{i,i} = 0\) and the matrix is symmetric, i.e. \(C_{i,j} = C_{j,i}\).

outputFormat

Output a single integer which is the minimum total cost for delivering packages to all cities from the depot and returning to the depot after each delivery.

## sample

3
0 1 3
1 0 5
3 5 0

8