题目描述

有一个包含 $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$ 到 $j$ 的有向边。如果 $i < j$，则这条边的权值为 $-1$，否则权值为 $1$。

りんごくん如果发现图中存在负环（即环上所有边的权值和小于 $0$），会非常难过。因此，他打算从すぬけさん新加的边中删除若干条，使得最终的图中不包含负环。删除すぬけさん新加的边 $(i \to j)$ 需要花费 $A_{i,j}$ 的代价。注意，最初存在的 $N-1$ 条边不能被删除。

请你求出，为了让最终的图中不包含负环，所需删除边的总代价的最小值。

输入格式

输入以如下格式从标准输入给出。

$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}$

输出格式

输出一个整数，表示为达成目标所需删除边的总代价的最小值。

样例 1

输入

3
2 1
1 4
3 3

输出

2

样例 2

输入

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

输出

2

样例 3

输入

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

说明/提示

数据范围

• $3 \leq N \leq 500$
• $1 \leq A_{i,j} \leq 10^9$
• 所有输入均为整数。

样例解释 1

如果删除すぬけさん新加的边 $(0 \to 1)$，则图中将不再有负环。此时所需总代价为 $2$，且这是最小值。

样例解释 2

如果删除すぬけさん新加的边 $(1 \to 2)$ 和 $(3 \to 0)$，则图中将不再有负环。此时所需总代价为 $1+1=2$，且这是最小值。

由 ChatGPT 4.1 翻译