P7751 [COCI 2013/2014 #2] PUTNIK

销售员 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 在飞行上消耗的最少时间。

#### 样例 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](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T4 PUTNIK_。** 按照原题数据配置，本题满分 $120$ 分。