\(1^{st}\) round, October \(20^{th}\), 2012

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:
 descendants of bacteria of the previous (K^{th}) generation are, in this order: {1, 2}, {3, 4}, {5, 6},
..., {\(2^{K} - 1\), \(2^{K}\)}
 descendants of bacteria of the older ((\(K-1\))^{th}) generation are, in this order: {1, 2, 3, 4}, {5, 6, 7,
8}, ..., {\(2^{K} - 3\), \(2^{K} - 2\), \(2^{K} - 1\), \(2^{K}\)}
 descendants of bacteria of the even older ((\(K-2\))^{th}) generation are, in this order: {1, 2, 3, 4, 5, 6,
7, 8}, ..., {\(2^{K} - 7\), \(2^{K} - 6\), \(2^{K} - 5\), \(2^{K} - 4\), \(2^{K} - 3\), \(2^{K} - 2\), \(2^{K} - 1\), \(2^{K}\)}
 ...
 descendants of the two bacteria of the second generation are, in this order: {1, 2, ..., \(2^{K}\)^{-1}} and
{\(2^{K}\)^{-1} + 1, \(2^{K}\)^{-1} + 2, ..., \(2^{K}\)}
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.
\(1^{st}\) round, October \(20^{th}\), 2012

The first line of input contains the positive integer K (\(1 \le K \le 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} \times 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.

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Contest 1