Description

给定一张 \(n\) 个点的带权无向图，点从 \(0\cdots n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短 Hamilton 路径。 Hamilton 路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点 恰好一次。

Input

第一行输入整数 \(n\)。

接下来 \(n\) 行每行 \(n\) 个整数，其中第 \(i\) 行第 \(j\) 个整数表示点 \(i\) 到 \(j\) 的距离（记为 \(a_{i,j}\)）。

对于任意的 \(x,y,z\)，数据保证 \(a_{x,x}=0，a_{x,y}=a_{y,x}\) 并且 \(a_{x,y}+a_{y,z}\ge a_{x,z}\)。

Output

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

Limitations

\(1\le n\le 20\)
\(0\le a_{i,j}\le 10^7\)

Sample

Sample #1

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

Source

算法竞赛进阶指南