该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

消圈策略

题目限制

1000 ms 256 M

题目描述

一个 $n$ 个点的有向带权图 $G$ （编号为 $1\sim n$ ），图中包含如下三种边：

1. 对于所有 $i\lt n$，有一条边权为 $0$ 的边 $i\rightarrow i+1$；

2. 对于所有 $i\lt j$，有一条边权为 $-1$ 的边 $i\rightarrow j$；

3. 对于所有 $i\gt j$，有一条边权为 $1$ 的边 $i\rightarrow j$；

我们会发现从 $i$ 到 $i+1$ 有 $2$ 条边，权值分别是 $0$ 和 $-1$。而从 $i+1$ 到 $i$ 仅 $1$ 条边，权值是 $1$。

你希望对图 $G$ 进行改造，使得 $G$ 中不存在负环，这就需要你选择一些边进行删除。每一条边删除的代价是不同的，给出每条边的删除代价，求将图 $G$ 改造为没有负环的图的最小代价。

**注意：**你不能够删除边权为 $0$ 的边。

输入格式

第一行：一个正整数n，表示点的数量（3≤n≤500） 之后n行：每行n-1个数a(i,j)，分别表示删去i到j的非0边需要的代价（由于不包括a(i,i)，所以是n-1个数）。

输出格式

输出一个数，表示改造的最小代价。

数据范围

对于6%的数据，$3 \le n \le 10$；

对于17%的数据，$3 \le n \le 100$；

对于100%的数据，$3 \le n \le 500, 1 \le a(i,j) \le 10^9$。

输入样例

3
2 1
1 4
3 3

输出样例

2

样例解释

图中存在 1→2,2→3,1→3 三条负权边，可能形成的负环只有1→2→3→1。

根据给出的数据：

a(1,2)=2,a(1,3)=1

a(2,1)=1,a(2,3)=4

a(3,1)=3,a(3,2)=3

因此去掉 1→2 这条边即可消除所有负环，代价最低。