题目描述

某乡有 $n$ 个村庄 $(1 \lt n \le 20)$，有一个售货员，他要到各个村庄去售货。

各村庄之间的路程 $S_{i,j}(0 \le S_{i,j} \le 1000)$ 是已知的，且 $i$ 村到 $j$ 村与 $j$ 村到 $i$ 村的路大多不同。

为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村（假设商店所在的村庄为 $1$）。

他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入格式

第一行包含一个整数 $n(1 \lt n \le 20)$，用于表示村庄数。

接下来 $n$ 行每行包含 $n$ 个整数，其中第 $i+1$ 行的第 $j$ 个数表示第 $i$ 个村庄到第 $j$ 个村庄的那条路的路程 $S_{i,j}(0 \le S_{i,j} \le 1000)$。

输出格式

输出一个整数，用于表示从商店出发到每个村庄一次，然后返回商店所在的村所需精力的最短路程。

样例

3
0 2 1
1 0 2
2 1 0

3

数据规模

对于100%的数据，满足 $1 \lt n \le 20, 0 \le S_{i,j} \le 1000$