题目描述

假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。目标是求出的路径是所有路径之中的最小值。

输入格式

第1行包含1个整数 $n（2\le n \le 15）$ 。

接下来输入一个 $n*n$ 的矩阵，表示两座城市之间的距离(距离均小于1000)。

矩阵对角线上的元素均为 $-1$（表示城市到自身的距离无定义）

输出格式

输出一个整数表示最小路程。

样例输入 #1

3
-1 1 10
1 -1 2
10 2 -1

样例输出 #1

13