문제

Author: Adrian Satja Kurdija

Scientists have discovered some strange bacteria on Mars and are now busy studying them. They have noticed that the number of bacteria is a power of 2, since each bacterium on Mars splits into two new bacteria (dying in the process), and it all started from a single bacterium. Thus, in the first generation there was a single bacterium. It split into two bacteria of the second generation, which split into four bacteria of the third generation, and so on – until the 2K bacteria of generation K+1 that the scientists have discovered. They have numbered the bacteria using numbers from 1 to 2K in the following way:  descendants of bacteria of the previous (Kth) generation are, in this order: {1, 2}, {3, 4}, {5, 6}, ..., {2K - 1, 2K}  descendants of bacteria of the older ((K-1)th) generation are, in this order: {1, 2, 3, 4}, {5, 6, 7, 8}, ..., {2K - 3, 2K - 2, 2K - 1, 2K}  descendants of bacteria of the even older ((K-2)th) generation are, in this order: {1, 2, 3, 4, 5, 6, 7, 8}, ..., {2K - 7, 2K - 6, 2K - 5, 2K - 4, 2K - 3, 2K - 2, 2K - 1, 2K}  ...  descendants of the two bacteria of the second generation are, in this order: {1, 2, ..., 2K-1} and {2K-1 + 1, 2K-1 + 2, ..., 2K} where curly braces denote a set of descendants of a single bacteria. That is, the 2K bacteria of the current generation were numbered such that descendants of any older bacterium have consecutive numbers. Notice that there exist many different permutations of these bacteria which still satisfy the rule that descendants of any older bacterium have consecutive sequence numbers. Scientists want to arrange the bacteria into such a sequence which also has the minimum possible length. The length of a bacteria sequence is the sum of distances between all neighbouring bacteria pairs. Specifically, there is a certain quantifiable repulsion between every two bacteria, which is the minimum distance between them if they are next to each other in the sequence. (Repulsion plays no role between bacteria that are not immediate neighbours in the sequence.) Given the repulsion values for all bacteria pairs, find the minimum possible length of a bacteria sequence (permutation) satisfying the descendant rule given above. Author: Adrian Satja Kurdija

입력

The first line of input contains the positive integer K (1 ≤ K ≤ 9) from the problem statement. Each of the following 2K lines contains 2K integers from the interval [0, 106]. These 2K × 2K numbers represent repulsion between bacteria pairs: the number in row m and column n is the repulsion between bacteria m and n. This number will, of course, be equal to the number in row n and column m. For m = n the number will be 0.

출력

The first and only line of output should contain the minimum possible length of a bacteria sequence satisfying the constraints.

예제 입력 1

2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

예제 출력 1

13

예제 입력 2

3
0 2 6 3 4 7 1 3
2 0 7 10 9 1 3 6
6 7 0 3 5 6 5 5
3 10 3 0 9 8 9 7
4 9 5 9 0 9 8 4
7 1 6 8 9 0 8 7
1 3 5 9 8 8 0 10
3 6 5 7 4 7 10 0

예제 출력 2

32