Problem Description

现在已经到了毕业季，小L打算实现高中之前的愿望：穷游中国。计划是这样的：小L打算从珠海出发，准备去若干个城市，最后再回到珠海。由于小L的经费有限，且每个城市只需去一次，小L就希望用最少的钱逛完所有的城市再回到珠海。题目假设每个城市之间都架设了高铁，并且给出了每个城市之间的高铁价格，现在让你求小L这次行程的最小花费。

Input

有多组数据，每组数据输入一个n（1 <= n <= 20），n代表城市的个数，接着给出一个n*n的矩阵，代表每两个城市之间的车票钱，

Output

每组数据输出一行，输出最小的车费花销。

Sample Input

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

Sample Output

15

Hint

共4个城市，1号城市为我们的起点珠海
车价小于10000

Author

zhbit_acmer