M. Mayor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ryei is the mayor of Chessland. His desire is to Chessland be a united and connected city. The citzens of Chessland (also known as pawns) live in their houses and they are afraid of walking through streets if it can go both ways, since they fear to be captured. For that reason, Ryei will design his streets to be one-way. He wants to connect all pawn's houses in a way that there is a directed path for every pair of houses using the fewest number of streets possible.

Ryei will construct his streets with Drex's Engineering, and they evaluated the costs of creating a street for each pair of houses. His budget is limited, so he wants to spend as little as possible. Answer the minimum total value he has to spend to achieve his goals using the fewest number of streets possible.

Input

The first line contains a single integer $$$n$$$ $$$(1\le n \le 10)$$$ — the number of houses.

The $$$i$$$'th of the next $$$n$$$ lines contains $$$n$$$ integers $$$c_{i,1}, c_{i,2}, ..., c_{i,n} $$$ $$$(0\le c_{i,j} \le 10^8)$$$ — where $$$c_{i,j}$$$ is the cost of building a street from house $$$i$$$ to house $$$j$$$.

Output

The output is a single integer $$$C$$$ — the minimum total cost to Ryei unite his city using the fewest number of streets possible.

Examples
Input
3
0 0 1
0 0 1
1 0 0
Output
1
Input
2
0 3
6 0
Output
9