009 - 発表会

問題

YDK学園では、毎年3月に一年間努力してきたことを発表する、通称「努力の跡」という発表会が行われます。発表するときには緊張しますがその緊張度は人によって異なり、また発表順によっても異なります。最初のほうに発表した方が緊張しないという人もいれば、最後のほうが緊張しないという人もいます。

YDK学園にはN人の生徒がおり、校長であるYTAは発表順による生徒の緊張具合をすべて記憶しています。具体的には、生徒iがj回目に発表するとき緊張度がA_i,jであることが分かっています。YTAは、生徒の緊張度の総和をできるだけ小さくしたいと思っています。そこで、最適な順番に選んだ時の生徒の緊張度の総和の最小値を求めてください。

入力

入力は以下の形式で行われる。

N
A1,1 A1,2 ... A1,N
A2,1 A2,2 ... A2,N
.
.
.
AN,1 AN,2 ... AN,N

1行目には、生徒の人数Nが与えられる。
続くN行にわたって各生徒の発表順による緊張度が与えられる。
i行目のj番目には生徒iがj番目に発表したときの緊張度A_i,jが与えられる。

出力

発表順を最適な順番にした際の生徒の緊張度の総和の最小値を求めよ

制約

1 ≦ N ≦ 20
0 ≦ A_i,j ≦ 10⁹

入出力例

入力例1

3
1 5 3
2 4 2
3 0 8

出力例1

3

この場合、発表順を1→3→2とすると緊張度の総和が最小になる。

入力例2

5
95 28 40 39 54
28 30 68 70 50
72 88 10 54 29
16 27 50 75 19
97 16 93 98 51

出力例2

112

MLEに気を付けて実装してください。