Round-Trip Optimizer

You're routing a delivery driver who must visit every city in a region exactly once and return to the starting depot. Given the pairwise distances between cities, find the minimum total distance of any such round trip.

Input

Line 1: an integer N — the number of cities (including the depot). Next N lines: N space-separated non-negative integers each. The j-th integer on the i-th line is the distance from city i to city j. The matrix is symmetric and the diagonal is zero.

City 0 is the depot — your route starts and ends there.

Output

A single integer: the minimum total distance of a route that starts at city 0, visits every other city exactly once, and returns to city 0.

Example

Input:

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

Output:

80

One optimal route is 0 → 1 → 3 → 2 → 0 with cost 10 + 25 + 30 + 15 = 80. Multiple orderings achieve the same total — you only need to report the cost, not the route.

Notes

• A natural starting point is to enumerate every possible ordering of cities and pick the cheapest — this works comfortably for small inputs.
• Greedy strategies (e.g., always travel to the nearest unvisited city) are simple to implement and often give reasonable results in practice.

Scoring

Your solution is evaluated against 10 test cases worth 10 points each (100 total). Read the problem carefully and pick your approach.