問題文

$1,2,...,N$ を並べ替えた順列がある。2つの異なる数字 $i$, $j$ を選んで入れ替えることを繰り返してソートされた状態( $1,2,...,N$ の順番に並んだ状態)にしたい。 数字 $i$, $j$ を入れ替える度にコストが $c_{i,j}$ 必要になる。

順列 $p$ に対して、 $p$ をソートするのに必要な最小コストを $f(p)$ とする。 $f(p)$ のとりうる最大値を求めよ。

入力

入力は以下のフォーマットに従う。与えられる数は全て整数である。

$N$
$c_{1,1}$ $c_{1,2}$ $...$ $c_{1,N}$
$c_{2,1}$ $c_{2,2}$ $...$ $c_{2,N}$
$...$
$c_{N,1}$ $c_{N,2}$ $...$ $c_{N,N}$

制約

• $2 \leq N \leq 8$
• $0 \leq c_{i,j} \leq 10^5$
• $c_{i,j} = c_{j,i}$
• $c_{i,i} = 0$

出力

最大値を1行に出力せよ。

Sample Input 1

3
0 1 3
1 0 8
3 8 0

Output for the Sample Input 1

5

もっとも必要コストが大きい順列は$\{1,3,2\}$で、

1. 1,2を入れ替えて$\{2,3,1\}$とする。
2. 1,3を入れ替えて$\{2,1,3\}$とする。
3. 1,2を入れ替えて$\{1,2,3\}$とする。

以上の操作によりコスト5でソートでき、またこれが最善であることが証明できる。 他の順列もコスト5以下でソートできることを示すことができる。