Description

Scientists have discovered some strange bacteria on Mars and are studying them. They noticed that the number of bacteria is a power of $2$, because each bacterium splits into two new bacteria, and initially there is one bacterium. Therefore, in the first generation there is only one bacterium, in the second generation there are two bacteria, in the third generation there are four bacteria, and so on, until in generation $K + 1$ there are $2^K$ bacteria.

The scientists numbered the bacteria with integers from $1$ to $2^K$ in the following way:

• The descendants of the generation $K$ bacteria, in order, are: $\{1,2\},\{3,4\},\{5,6\},\cdots,\{2^K-1,2^K\}$.
• The descendants of the generation $K - 1$ bacteria, in order, are: $\{1,2,3,4\},\{5,6,7,8\},\cdots,\{2^K-3,2^K-2,2^K-1,2^K\}$.
• The descendants of the generation $K - 2$ bacteria, in order, are: $\{1,2,3,4,5,6,7,8\},\cdots,\{2^K-7,2^K-6,2^K-5,2^K-4,2^K-3,2^K-2,2^K-1,2^K\}$.
• $\cdots$
• The descendants of the generation $1$ bacteria, in order, are: $\{1,2,\cdots,2^{K-1}\},\{2^{K-1}+1,2^{K-1}+2,\cdots,2^K\}$.

Here, the curly braces represent the set of descendants of one bacterium.

In other words, we number the $2^K$ bacteria in the current generation so that the descendants of any older bacterium have consecutive numbers. Note that there are many different permutations that still satisfy the condition that the descendants of any older bacterium have consecutive numbers.

The scientists want to arrange the bacteria into a sequence with the shortest possible length. The length of a bacteria sequence is the sum of the distances between all adjacent pairs of bacteria.

More precisely, there is a certain repulsion value between every pair of bacteria. If they are adjacent in the sequence, this repulsion value is the distance between them (repulsion values between non-adjacent bacteria do not matter). Given the repulsion values for all pairs of bacteria, find the minimum possible length of a bacteria sequence (permutation) that satisfies the descendant rule above.

Input Format

The first line contains a positive integer $K$, as described above.

The next $2^K$ lines each contain $2^K$ integers in the range $[0,10^6]$. These $2^K \times 2^K$ integers represent the repulsion values between pairs of bacteria: the integer in row $m$ and column $n$ is the repulsion value between bacterium $m$ and bacterium $n$. Of course, this integer is equal to the integer in row $n$ and column $m$. If $m=n$, this integer will be $0$.

Output Format

Output one line with one integer, the minimum possible length of a bacteria sequence that satisfies the conditions.

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

13

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

32

Hint

Constraints

For $100\%$ of the testdata, $1 \le K \le 9$.

Notes

The score for this problem follows the original COCI settings, with a full score of $160$.

This problem is translated from COCI2012-2013 CONTEST #1 T6 MARS.

Translated by ChatGPT 5