問題文

Aさんはあるアイドル事務所のマネージャーです。
このアイドル事務所にはｎ人（2の倍数人）のアイドルが登録しています。
全員2人組（ペア）にして売り出すことになりました。
全部の2人には相性があり、2人の相性度の高さがそのままアイドルの人気度になります。
2人をa,bとして相性度を求める関数をｆとするとf(a,b)=f(b,a)となります。
全2人の組み合わせでの相性度がｎ*ｎの表で与えられる。（f（a,a）は不可能なので-1が与えられる。）
全ペアの人気度の合計が最大になるようにペアを作った時の合計人気度を答えよ。
(ヒント　最も重い採点データn=24をRubyで安定して一秒以内が想定解です、C++では0.1秒以内)

入力

$n$
$F11$ $\dots$ $F1n$
$\dots$
$Fn1$ $\dots$ $Fnn$

1<n<=24

0<=fij<=1000

アイドルの人数ｎ人が一行目に与えられる。 続くｎ行にｎ*ｎの表として、アイドルの相性表が与えられる。
一行目がアイドル１で２行目がアイドル２、、、ｎ行目がアイドルN
一列目がアイドル１で２列目がアイドル２、、、ｎ列目がアイドルN
例えばアイドル１とアイドル３の相性を見るには１行目の３列目か３行目の１列目を見ればよい。 アイドル２とアイドル7の相性を見るには２行目の７列目か7行目の２列目を見ればよい。 $S$と一行に全ペアの人気度の合計値が最大になるようにペアを作った時の人気度を表示せよ。

出力

S 最後に改行してください。

サンプル

4
-1 16 15 38
16 -1 22 17
15 22 -1 19
38 17 19 -1

60

6
-1 14 29 35 39 8
14 -1 35 41 34 3
29 35 -1 14 21 21
35 41 14 -1 12 42
39 34 21 12 -1 28
8 3 21 42 28 -1

116