巡回训练（tour）

题目描述

$\text{DAMON THRONE}$ 有 $n$ 个训练基地，编号为 $1$ 到 $n$，从基地 $i$ 前往基地 $j$ 需要花费 $c_{i,j}$ 点能量。

小 D 从基地 $1$ 出发，需要访问每个训练基地恰好一次，最后回到基地 $1$。

也就是说，他需要选择一个排列：

满足：

且 $1$ 到 $n$ 中的每个编号恰好出现一次。

这次巡回训练的总能量消耗为：

请你求出完成巡回训练所需要的最小能量。

输入格式

第一行包含一个整数 $n$，表示训练基地数量。

接下来 $n$ 行，每行包含 $n$ 个整数。

第 $i$ 行第 $j$ 个整数为 $c_{i,j}$，表示从基地 $i$ 前往基地 $j$ 的能量消耗。

输出格式

输出一行一个整数，表示完成巡回训练所需要的最小能量。

输入输出样例 #1

输入 #1

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

输出 #1

80

样例解释 #1

一种最优的巡回路线为 $1\rightarrow2\rightarrow4\rightarrow3\rightarrow1$，总能量消耗为 $10+25+30+15=80$ 。

可以证明，不存在能量消耗更小的巡回路线。

输入输出样例 #2

输入 #2

3
0 4 7
6 0 5
3 8 0

输出 #2

12

样例解释 #2

可以选择路线 $1\rightarrow2\rightarrow3\rightarrow1$，总能量消耗为 $4+5+3=12$，另一条路线 $1\rightarrow3\rightarrow2\rightarrow1$，总能量消耗为 $7+8+6=21$，所以最小能量为 $12$。

输入输出样例 #3

输入 #3

1
0

输出 #3

0

样例解释 #3

只有一个训练基地，小 D 不需要移动，因此能量消耗为 $0$。

数据范围与约定

对于所有测试数据，保证：

对于任意 $i\ne j$，保证：

从基地 $i$ 到基地 $j$ 的能量消耗不一定等于从基地 $j$ 到基地 $i$ 的能量消耗。

特殊性质 $\text{A}$：保证对于任意 $i,j$，都有 $c_{i,j}=c_{j,i}$。

特殊性质 $\text{B}$：保证所有 $i\ne j$ 的 $c_{i,j}$ 都相同。

特殊性质 $\text{C}$：保证 $c_{i,j}=|i-j|+1$。