Final Trip

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

Striving Panda 这个暑假就要毕业去上海了,当然也不会在这里进行集训,如此长的假期,他打算充分利用这一段时间来把在南京没有参观过的景点游览一次。 他仔细想了想,发现有n个景点他没有去过,所以他决定都去参观。他设想一种方案:从学校出发,依次游览这n个景点(每个景点必须游览且只游览一次),再从最后一个景点回到学校。我们知道 ,学校不是景点。另外Panda得到了一个优惠证,他从学校到任一个景点以及任一个景点到学校的费用都是免费的,但是 从第i个景点到第j个景点的路途费用是cost[i][j] 。 出于资金问题,他不想把主要费用花费在路途上,所以他想找一种最优的游览顺序,使得他在路途的总费用最少。你能帮他计算最少要多少费用吗?

Input

每个测试给定n(<=18),表示n个景点,然后给出n*n的方阵,第i行j列说明从景点i到景点j的费用是cost[i][j]。 文件以EOF结尾。

Output

每个Input输出1个数,表示总的最小费用。

Sample Input

2
0 1
2 0
4

0 3 6 7

5 0 3 5

6 2 0 9

1 2 7 0

Sample Output

1
7

Hint

Case 1: 学校->景点1->景点2->学校 Case 2: 学校->景点4->景点1->景点2->景点3->学校

Source

ghostplant

提交代码