时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一张 \(n\) 个点的带权无向图，点从 \(0 \sim n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短哈密顿路径。

　　哈密顿路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。

【输入格式】

　　一行输入整数 \(n\)。
　　接下来 \(n\) 行每行 \(n\) 个整数，其中第 \(i\) 行第 \(j\) 个整数表示点 \(i-1\) 到 \(j-1\) 的距离（记为 \(a[i-1,j-1]\)）。
　　对于任意的 \(x,y,z\)，数据保证 \(a[x,x]=0，a[x,y]=a[y,x]\) 并且 \(a[x,y]+a[y,z] \ge a[x,z]\)。

【输出格式】

　　输出一个整数，表示最短哈密顿路径的长度。

【输入输出样例】

　Input

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

　Output

18

【数据限制】

　　对于所有测试数据满足 \(1 \le n \le 20\)，\(0 \le a[i,j] \le 10^7\)

【来源】

　　Mr.he