【题意简述】

有一个 $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$。