题目描述

给定一张 $\red{n}$ 个点的带权无向图，点从 $\red{0}$~$\red{n-1}$ 标号，求起点 $\red{0}$ 到终点 $\red{n-1}$ 的最短Hamilton路径。

Hamilton路径的定义是从 $\red{0}$ 到 $\red{n-1}$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数$\red{n}$。

接下来$\red{n}$行每行$\red{n}$个整数，其中第$\red{i}$行第$\red{j}$个整数表示点$\red{i}$到$\red{j}$的距离（记为$\red{a[i,j] }$ ）。

对于任意的$\red{x,y,z}$，

数据保证 $\red{a[x,x]=0}$，$\red{a[x,y]=a[y,x]}$

并且 $\red{a[x,y]+a[y,z]>=a[x,z]}$。

输出格式

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

样例

输入数据

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

输出数据

18

提示

$\red{1≤n≤20}$

$\red{0≤a[i,j]≤10^7}$