题目描述

销售员 Sept 有一个任务，即游览 $N$ 座城市（从 $1$ 到 $N$ 编号），每座城市只能游览恰好一次。

这 $N$ 座城市中，每两座之间都有一列航班。Sept 追求效率，所以他希望在飞行上消耗的时间最少。为此，他可以调整这些城市的游览顺序。

但 Sept 对这个游览顺序有一个奇怪的要求：

• 对于城市 $1$ 没有要求。
• 如果要游览城市 $K(K\in[2,N])$，则所有编号小于 $K$ 的城市，要么都在游览城市 $K$ 前游览完，要么都在游览城市 $K$ 后游览完。
  换句话说，对于两个城市 $X,Y(1\le X,Y< K)$，不能在城市 $K$ 前游览城市 $X$ 而在城市 $K$ 后游览城市 $Y$。

在这些限制下，给定每两座城市之间乘坐航班所需的时间，求出 Sept 在飞行上消耗的最少时间。

输入格式

第一行一个整数 $N$，即城市的数量。

接下来 $N$ 行 $N$ 列整数。我们令 $(A,B)$ 表示第 $A$ 行的第 $B$ 个数，则有

• $(A,B)$ 表示城市 $A,B$ 之间乘坐航班所需的时间。
• 若 $A=B$，$(A,B)=0$。
• $(A,B)=(B,A)$。

输出格式

仅一行一个整数，即 Sept 在飞行上消耗的最少时间。

3 
0 5 2 
5 0 4 
2 4 0

7

4 
0 15 7 8 
15 0 16 9 
7 16 0 12 
8 9 12 0

31

提示

样例 1 说明

顺序 $\tt2,1,3$ 或 $\tt3,1,2$ 都是可以的。

注意到 $\tt1,3,2$ 用时更短，但不符合 Sept 的奇怪要求。

样例 2 说明

顺序 $\tt3,1,2,4$ 或 $\tt4,2,1,3$ 都是可以的。

数据规模与约定

本题不采用捆绑测试，在评测中也不会体现 Subtask。

• Subtask 1 $\tt(40pts)$：$2\le N\le 10$。
• Subtask 2 $\tt(20pts)$：$2\le N\le 20$。
• Subtask 3 $\tt(60pts)$：无特殊限制。

对于 $100\%$ 的数据，有 $2\le N\le 1500$，$0\le (A,B)\le 10^3$。

来源

本题译自 COCI2013-2014 CONTEST 2 T4 PUTNIK。

按照原题数据配置，本题满分 $120$ 分。