Problem Statement

There are $N$ squares, numbered $1, 2, \dots, N$.
On each square lies one card that is red on one side and white on the other, and initially all cards have the red side up.
A-kun wants to flip the cards one at a time so that all of them have the white side up, but B-kun, who likes the color red, interferes with this.
The two act as follows.

0. First, A-kun chooses any $1$ square he likes and flips its card so that the white side is up.

1. A-kun chooses $1$ square from those with the red side up and flips its card so that the white side is up.
Letting $q$ be the square chosen at this time and $p$ be the square chosen just before it, a cost of $c_{p,q} (>0)$ is incurred.

2. B-kun flips the card on square $p$, the square A-kun chose just before, so that the red side is up.
However, if he has previously flipped the card on square $p$, he does nothing.

3. Repeat 1. and 2. The game ends as soon as all cards are white and B-kun has done nothing.

Input

$N$
$c_{1,1}$ $c_{1,2}$ $\dots$ $c_{1,N}$
$c_{2,1}$ $c_{2,2}$ $\dots$ $c_{2,N}$
$\vdots$
$c_{N,1}$ $c_{N,2}$ $\dots$ $c_{N,N}$

・All input values are integers.
・$2 \le N \le 9$
・$c_{i,i} = 0$
・$1 \le c_{i,j} \le 10^8$ $(i \neq j)$

Output

Output the minimum possible total cost incurred until the game ends.

Sample

2
0 10
20 0

40

3
0 7 3
9 0 2
6 5 0

15

6
0 15024 31317 93469 62177 4320
49893 0 44972 34509 76317 68434
45883 5950 0 24246 41070 55112
86178 14298 54193 0 38052 3009
59166 59527 55171 91031 0 1398
88688 30894 42756 4816 93098 0

193095