"I am going to be the pirate king!" Luffy shouted such a slogan, and along with his partners on the difficult journey of the grand line.

The starting point for Luffy's grand line is Logue town, and the end is Rough Tale (where the only secret treasure is hidden - ONE PIECE). In the middle of the voyage, there are a variety of islands.

Because the climate on the grand line is very unusual, the time to commute between any two islands varies greatly. It may take 1 day from island A to island B, but 1 year from island B to island A. Of course, the sailing time between any two islands is different, but it is predictable.

Now suppose that Luffy and his partners start from Logue town (starting point), traverse all the islands in the middle of the grand line (but the islands that have been visited cannot be visited again), and finally arrive at Rough Tale (end point). Suppose they don't make any stops on the islands. What’s the minimum time they spent on sailing to successfully reach the end point.

The input data contains multiple lines. The first line contains an integer N (2 < N ≤ 16), representing a total of N islands on the grand line (including the starting point of Logue town and the end of Rough Tale). Wherein, the starting point is denoted as 1, and the ending as N. The following N lines each line contains N integers, wherein the jth (1 ≤ j ≤ N) integers of the i-th (1 ≤ i ≤ N) line represent The time t (0 < t < 10000) required to travel from the i-th island to the j-th island. The i-th integer in the i-th row is 0.

The output is an integer representing the minimum time required for the Luffy to reach the end point after traversing all intermediate islands (not repeated) from the starting point.