配点 : $1200$ 点

問題文

$N$ 頂点からなる重み付き有向グラフがあり、頂点には $0$ から $N-1$ までの番号がついています。

最初、このグラフには $N-1$ 本の辺があります。 このうち $i$ 番目 ($0 \leq i \leq N-2$) の辺は、 頂点 $i$ から頂点 $i+1$ へ向かう重さ $0$ の辺です。

すぬけさんはこれから、全ての $i,j$ ($0 \leq i,j \leq N-1,\ i \neq j$) について、新たに辺 $(i \to j)$ を追加する操作を行います。 辺の重さは、$i < j$ なら $-1$、そうでないなら $1$ とします。

りんごくんは、グラフに負閉路（閉路であって、そこに含まれる辺の重みの総和が $0$ 未満のもの）があるととても悲しいです。 そこで、すぬけさんが追加した辺のうちいくつかを削除して、最終的なグラフに負閉路が含まれないようにすることにしました。 すぬけさんが追加した辺 $(i \to j)$ を削除するには $A_{i,j}$ のコストがかかります。 なお、最初からあった $N-1$ 本の辺を削除することはできません。

りんごくんが目的を達成するために必要なコストの総和の最小値を求めてください。

制約

• $3 \leq N \leq 500$
• $1 \leq A_{i,j} \leq 10^9$
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_{0,1}$ $A_{0,2}$ $A_{0,3}$ $\cdots$ $A_{0,N-1}$

$A_{1,0}$ $A_{1,2}$ $A_{1,3}$ $\cdots$ $A_{1,N-1}$

$A_{2,0}$ $A_{2,1}$ $A_{2,3}$ $\cdots$ $A_{2,N-1}$

$\vdots$

$A_{N-1,0}$ $A_{N-1,1}$ $A_{N-1,2}$ $\cdots$ $A_{N-1,N-2}$

出力

りんごくんが目的を達成するために必要なコストの総和の最小値を出力せよ。

3
2 1
1 4
3 3

2

すぬけさんが追加した辺 $(0 \to 1)$ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $2$ で、これが最小です。

4
1 1 1
1 1 1
1 1 1
1 1 1

2

すぬけさんが追加した辺 $(1 \to 2)$ と $(3 \to 0)$ を削除すると、グラフに負閉路がないようになります。 この時必要なコストは $1+1=2$ で、これが最小です。

10
190587 2038070 142162180 88207341 215145790 38 2 5 20
32047998 21426 4177178 52 734621629 2596 102224223 5 1864
41 481241221 1518272 51 772 146 8805349 3243297 449
918151 126080576 5186563 46354 6646 491776 5750138 2897 161
3656 7551068 2919714 43035419 495 3408 26 3317 2698
455357 3 12 1857 5459 7870 4123856 2402 258
3 25700 16191 102120 971821039 52375 40449 20548149 16186673
2 16 130300357 18 6574485 29175 179 1693 2681
99 833 131 2 414045824 57357 56 302669472 95
8408 7 1266941 60620177 129747 41382505 38966 187 5151064

2280211