光之邮递员负责在艾欧泽亚大陆递送邮件，他们的行程的起点是森都格里达尼亚，终点是乌尔达哈。途中，会经过是各式各样的城镇送信。

因为艾欧泽亚大陆的气候十分异常，所以来往任意两个城镇之间的所需要时间差别很大，从A镇到B镇可能需要3天，而从B镇到A镇则可能需要1年。当然，任意两个城镇之间的行程时间虽然差别很大，但都是已知的。 

现在假设光之邮递员从森都（起点）出发，遍历艾欧泽亚大陆中所有的城镇送信（但是已经经过的城镇不能再次经过），最后到达乌尔达哈（终点）。假设他们在城镇中送信不作任何的停留，请问，他们最少需要花费多少时间才能到达终点？ 

The Postman of Light is responsible for delivering mail in Eorzea. The starting point of their itinerary is Gridania and the end point is Ul’dah. On the way, you will pass through various towns and cities.

Because the climate of Eorzea is very abnormal, the time required to travel between any two towns is very different. It may take 3 days from Town A to Town B, and it may take 1 year from Town B to Town A. Of course, although the travel time between any two towns varies greatly, they are all known.

Now suppose that the postman of light sets off from Gridania(the starting point), traverses all the towns in the Eorzea continent to deliver the letter (but the towns that have passed can not be passed through again), and finally arrives at Ul’dah (the end). Suppose they don’t make any stops in the town to deliver letters. How long will it take for them at least to reach the destination?

输入数据包含多行。 第一行包含一个整数N(2 < N ≤ 16)，代表艾欧泽亚大陆上一共有N个城镇（包含起点的格里达尼亚和终点的乌尔达哈）。

其中，起点的编号为1，终点的编号为N。 之后的N行每一行包含N个整数，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个城镇出发到第j个城镇需要的时间t(0 < t < 10000)。

第i行第i个整数为0。

The input data contains multiple lines.
The first line contains an integer N (2 <N ≤ 16), representing a total of N towns on the Eorzea continent (including Gridania at the starting point and Ul’dah at the ending point).

Among them, the number of the start point is 1, and the number of the end point is N. Each of the following N rows contains N integers, where the jth (1 ≤ j ≤ N) integer in the i-th row (1 ≤ i ≤ N) represents the time required to depart from the i-th town to the j-th town t(0 <t <10000).

The i-th integer in the i-th row is 0.

输出输出为一个整数，代表光之邮递员从起点遍历所有中间城镇（不重复）之后到达终点所需要的最少的时间。

The output is an integer, which represents the minimum time it takes for the Postman of Light to reach the end after traversing all intermediate towns(not repeated) from the starting point.