Optimal Bacteria Ordering

Scientists on Mars discovered strange bacteria that reproduce by splitting. Initially there is one bacterium; in the first generation there is 1 bacterium, in the second 2, in the third 4, and so on. In general, in the $(K+1)$-th generation there are $2^K$ bacteria. The bacteria are numbered with the integers from $1$ to $2^K$ according to the following rules:

• The descendants of each bacterium in generation $K$ are numbered in consecutive pairs: $\{1,2\},\{3,4\},\{5,6\},\dots,\{2^K-1,2^K\}$.
• The descendants of each bacterium in generation $K-1$ are numbered in consecutive groups of four: $\{1,2,3,4\},\{5,6,7,8\},\dots,\{2^K-3,2^K-2,2^K-1,2^K\}$.
• In general, for any older bacterium, the set of its descendant bacteria receives consecutive numbers.

Note that many different permutations of the $2^K$ bacteria satisfy the property that the descendants of any older bacterium appear consecutively. The scientists now want to arrange the bacteria in a sequence (which is a permutation of the numbers $1$ to $2^K$) that respects this descendant rule and minimizes the total "length" of the sequence. The length of a sequence is defined as the sum of the distances (given by a pairwise rejection value) between every two consecutive bacteria in the sequence. That is, if two bacteria appear adjacent in the sequence, their contribution to the overall length is the rejection value between them (rejection values for non‐adjacent bacteria do not contribute).

Given the rejection values for every pair of bacteria, find the permutation that obeys the descendant‐continuity rule and has the minimum total adjacent rejection sum.

The rejection value between bacterium i and bacterium j is denoted by $R_{ij}$.

inputFormat

The first line contains a single integer $K$ ($K \ge 1$). This implies that there are $2^K$ bacteria.

The next $2^K$ lines each contain $2^K$ integers. The $j$-th integer on the $i$-th line denotes the rejection value $R_{ij}$ between bacterium i and bacterium j. It is guaranteed that $R_{ii} = 0$ and that the matrix is symmetric.

outputFormat

Output a single integer: the minimum total length of a valid bacteria sequence satisfying the descendant continuity rule.

sample

1
0 1
1 0

1