Sort

Time Limit : 2 sec, Memory Limit : 65536 KB

問題文

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以下でソートできることを示すことができる。


Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18