该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

徐老师是一个旅行商人。他要去推销产品的的一共有 $N$ 个城市。 城市编号分别为 $1, 2, \cdots, N$ 。

因为徐老师囊中羞涩，所以整个旅行过程，他都需要乘坐公交。

当前徐老师在 $1$ 号城市。现在告诉你任意两个城市之间是否有公交可以到达，问是否存在一条旅行路线能够从 $1$ 号城市出发，访问 $2, 3, \cdots, N$ 号城市各一次，且最后能回到 $1$ 号城市。若是存在，徐老师希望知道整个旅程的最短路程。

输入格式

第一行一个整数 $N$（$2\leq N \leq 10$），表示城市个数。

接下来 $N$ 行，每行 $N$ 个数字。第 $i$ 行第 $j$ 列的数字的值：

输出格式

如果存在这样的旅行路径，输出一个正整数，表示最短距离；否则输出 -1。

答案不会超过 int 的范围。

样例

6
0 9 9 0 0 2
0 0 3 0 9 1
0 5 0 5 0 8
6 0 8 0 0 0
0 1 0 0 0 5
5 2 8 1 0 0

35