描述

给定 n 个城市和它们之间的距离。一位商人从城市 1 出发，需要走遍所有其他城市一次且仅一次。请你找出总距离最短的路径。

格式

输入

输入包含多个测试用例。 输入的第一行是一个整数 n (1 <= n <= 20)，代表城市的数量。 接下来是一个 n x n 的矩阵 dis，其中 dis[i][j] 表示从城市 i 到城市 j 的距离。城市的编号为 1 到 n。

1 <= dis[i][j] <= 10000

输出

输出一个整数，代表走遍所有城市所需的最短总距离。

样品

input1

3
0 2 3
1 0 3
3 1 0

output1

4

限制

对于每个测试用例： 时间限制: 1s