問題文

$N$ 個のマスがあり、それぞれ $1, 2, \dots, N$ と番号が振られています。
各マスには片面が赤、もう片面が白のカードが一枚置いてあり、最初は全て赤が表になっています。
A君はカードを一枚ずつ裏返して全て白が表になっている状態にしたいと思いましたが、赤色が好きなB君はこれを邪魔します。
二人は以下のように行動します。

0. はじめにA君が好きなマスを $1$ つ選び、カードを裏返して白を表にする。

1. A君は赤が表になっているマスから $1$ つ選び、カードを裏返して白を表にする。
この時に選んだマスを $q$ 、一つ前に選んだマスを $p$ としたとき、コスト $c_{p,q} (>0)$ がかかる。

2. B君は、A君が一つ前に選んだマス $p$ のカードを裏返し、赤を表にする。
ただし、それ以前にマス $p$ のカードを裏返したことがある場合は何もしない。

3. 1. 2. を繰り返す。全てのカードが白であり、かつB君が何もしなかった時点でゲームを終了する。

入力

$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}$

・入力は全て整数である。
・$2 \le N \le 9$
・$c_{i,i} = 0$
・$1 \le c_{i,j} \le 10^8$ $(i \neq j)$

出力

ゲーム終了までにかかるコストの総和の最小値を出力してください。

サンプル

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