프로그램 명: coci_mars
제한시간: 1 초

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 2^K bacteria of generation K+1 that the scientists have discovered. They have numbered the bacteria using numbers from 1 to 2^K in the following way:

where curly braces denote a set of descendants of a single bacteria. That is, the 2^K 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.

입력

The first line of input contains the positive integer K (1 ≤ K ≤ 9) from the problem statement. Each of the following 2^K lines contains 2^K integers from the interval [0, 10^6 ]. These 2^K × 2^K 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.

입출력 예

input

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

output

13

input

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

output

32

출처:coci/2012-2013/contest1 6/6
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]