题目描述

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

输入格式

第一行一个整数 n。 接下来 n 行，每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到点 j 的距离 a[i][j]。

输出格式

一个整数，表示最短 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

数据范围

1 ≤ n ≤ 20，0 ≤ a[i][j] ≤ 10^7。 保证 a[x][x] = 0，a[x][y] = a[y][x]，且 a[x][y] + a[y][z] ≥ a[x][z]。