Mars Bacteria Lineup

Scientists discovered unusual bacteria on Mars. The population starts from one bacterium. In each generation, every bacterium splits into two bacteria and the original one disappears. Therefore, generation $K+1$ contains $2^K$ bacteria.

The scientists numbered the bacteria in the last generation from 1 to $2^K$. The numbering has the property that the descendants of every ancestor form a consecutive interval of numbers. The descendants of the generation $K$ bacteria are $\{1,2\}$, $\{3,4\}$, ..., $\{2^K-1,2^K\}$, and the descendants of the generation $K-1$ bacteria are consecutive intervals of size 4. In the same way, the descendants of the two generation 2 bacteria are $\{1,2,\ldots,2^{K-1}\}$ and $\{2^{K-1}+1,\ldots,2^K\}$.

When the bacteria are rearranged, this property must still hold: for every ancestor bacterium, all of its descendants must occupy one consecutive block in the new order. Equivalently, in the complete binary tree representing the genealogy, each internal node may independently swap the order of its left and right descendant groups.

A repulsion value is given for every pair of bacteria. If two bacteria become adjacent in the new order, the distance between them must be at least their repulsion value. The length of an order is the sum of the distances between every adjacent pair. Find the minimum possible length of an order that satisfies the genealogy condition.

The first line contains a positive integer $K$. $(1 \le K \le 9)$

The next $2^K$ lines contain the repulsion matrix. Each line contains $2^K$ integers, and every value is between $0$ and $10^6$, inclusive. The number in row $m$ and column $n$ is the repulsion between bacterium $m$ and bacterium $n$. The matrix is symmetric, and the repulsion of a bacterium with itself is $0$.

Output the minimum possible length of a valid order.