problem （from luogu）
有一个 \(N\) 个点的有向图，节点标号为 \(0 \sim (N - 1)\)。
这张图初始时只有 \(N - 1\) 条边，每条边从 \(i\) 指向 \(i + 1\)，边权为 \(0\)。
对于每一对 \(i, j\)（\(0 \le i, j \le N - 1\)，\(i \ne j\)），Snuke 会加入新边 \(i \to j\)，如果 \(i < j\) 则边权为 \(-1\)，否则边权为 \(1\)。
Ringo 不喜欢图中的负环，所以他想要删掉一些 Snuke 加入的边，使得最终得到的图没有负环。
但是删掉每一条边是有代价的，具体地说，删掉 \(i \to j\) 这条边，要花费 \(A_{i, j}\) 的代价。
请问满足图中不存在负环的最小删边代价是多少？
- \(3 \le N \le 500\)，\(1 \le A_{i, j} \le {10}^9\)。
solution
考虑差分约束模型：图中不存在负环，当且仅当差分约束有解。
那么题目的限制是这样的：
- 对于 \(i<j\) 满足 \(s_i-1\geq s_j\Leftrightarrow s_j-s_i\geq 1\)。我们称之为一类边。
- 对于 \(i>j\) 满足 \(s_i+1\geq s_j\Leftrightarrow s_i-s_j\leq 1\)。我们称之为二类边。
- \(s_i\geq s_{i+1}\) 恒成立。