问题描述

我是要成为海贼王的男人！”

路飞他们伟大航路行程的起点是罗格镇，终点是拉夫德鲁（那里藏匿着“唯一的大秘宝”——ONE PIECE）。而航程中间，则是各式各样的岛屿。

因为伟大航路上的气候十分异常，所以来往任意两个岛屿之间的时间差别很大，从 $A$ 岛到 $B$ 岛可能需要 $1$ 天，而从 $B$ 岛到 $A$ 岛则可能需要 $1$ 年。当然，任意两个岛之间的航行时间虽然差别很大，但都是已知的。

现在假设路飞一行从罗格镇（起点）出发，遍历伟大航路中间所有的岛屿（但是已经经过的岛屿不能再次经过），最后到达拉夫德鲁（终点）。假设他们在岛上不作任何的停留，请问，他们最少需要花费多少时间才能到达终点？

输入格式

输入输入数据包含多行。
第一行包含一个整数 $N(2 < N ≤ 16)$，代表伟大航路上一共有$N$个岛屿（包含起点的罗格镇和终点的拉夫德鲁）。其中，起点的编号为 $1$，终点的编号为 $N$。
之后的N行每一行包含 $N$ 个整数，其中，第 $i(1 ≤ i ≤ N)$ 行的第 $j(1 ≤ j ≤ N)$ 个整数代表从第 $i$ 个岛屿出发到第 $j$ 个岛屿需要的时间 $t(0 < t < 10000)$。第 $i$ 行第 $i$ 个整数为 $0$。

输出格式

输出输出为一个整数，代表路飞一行从起点遍历所有中间岛屿（不重复）之后到达终点所需要的最少的时间。

样例输入与输出

4
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0

100

5
0 18 13 98 8
89 0 45 78 43
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0

137

数据范围

• 对于$20\%$的测试数据: $2<N≤5$
  
• 对于$60\%$的测试数据: $2<N≤10$
  
• 对于全部的测试数据: $2<N≤16, 0 < t < 10000$