问题描述

我们有一个有向带权图，其中有 $N$ 个顶点，编号从 $0$ 到 $N-1$。

图最初有 $N-1$ 条边。第 $i$ 条边（$0 \leq i \leq N-2$）从顶点 $i$ 指向顶点 $i+1$，权重为 $0$。

Snuke 现在会为每对顶点 $i, j$ （$0 \leq i,j \leq N-1, i \neq j$）添加一条新的边 $(i \to j)$。如果 $i < j$，边的权重为 $-1$；否则为 $1$。

Ringo 是个男孩。图中存在一个总权重为负的负权回路会让他难过。他将删除 Snuke 添加的一些边，以便图中不再含有负权回路。删除边 $(i \to j)$ 的代价为 $A_{i,j}$。他不能删除一开始就存在的边。

找到实现 Ringo 目标所需的最小总代价。

约束条件

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

输出

输出实现 Ringo 目标所需的最小总代价。

示例输入 1

3
2 1
1 4
3 3

示例输出 1

2

如果删除 Snuke 添加的边 $(0 \to 1)$，图中将不再含有负权回路。在这种情况下，代价为 $2$，是可能的最小值。

示例输入 2

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

示例输出 2

2

如果删除 Snuke 添加的边 $(1 \to 2)$ 和 $(3 \to 0)$，图中将不再含有负权回路。在这种情况下，代价为 $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

示例输出 3

2280211