P7587 [COCI 2012/2013 #1] MARS

科学家在火星上发现了一些奇怪的细菌，正在研究它们。他们注意到细菌的数量是 $2$ 的次方，因为每一种细菌都会分裂成两种新的细菌，而初始有一种细菌。因此，在第一代中只有一种细菌，第二代中有两种细菌，第三代中有四种细菌，以此类推，直到第 $K + 1$ 代中有 $2^K$ 种细菌。 科学家们用 $1$ 至 $2^K$ 之间的整数给细菌进行了编号，方法如下： - 第 $K$ 代细菌的后代按顺序分别为：$\{1,2\},\{3,4\},\{5,6\},\cdots,\{2^K-1,2^K\}$ - 第 $K - 1$ 代细菌的后代按顺序分别为：$\{1,2,3,4\},\{5,6,7,8\},\cdots,\{2^K-3,2^K-2,2^K-1,2^K\}$ - 第 $K - 2$ 代细菌的后代按顺序分别为：$\{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$ - 第 $1$ 代细菌的后代按顺序分别为：$\{1,2,\cdots,2^{K-1}\},\{2^{K-1}+1,2^{K-1}+2,\cdots,2^K\}$ 其中花括号表示一个细菌的一组后代。 也就是说，对当前这一代的 $2^K$ 个细菌进行编号，使得任何较老细菌的后代都有连续的编号。**注意这些细菌存在许多种不同的 仍然满足任何较老细菌的后代都有连续编号的条件 的排列。** 科学家想把细菌排列成一个**长度尽可能短**的序列。细菌序列的长度是**所有相邻的细菌对之间的距离的总和**。 确切地说，每两个细菌之间都有一定的**排斥值**。如果它们在序列中相邻，这个排斥值就是它们之间的最小距离（序列中不相邻的细菌之间的排斥值不起作用）。给定所有细菌对的排斥值，找出满足上述后代规则的细菌序列（排列）的最小长度。

输入的第一行包含一个正整数 $K$，意义见题目描述。 接下来的 $2^K$ 行，每行包含在 $[0,10^6]$ 范围内的 $2^K$ 个整数。这 $2^K \times 2^K$ 个整数表示细菌对之间的排斥值：第 $m$ 行第 $n$ 列中的整数是细菌 $m$ 和细菌 $n$ 之间的排斥值。当然这个整数等于第 $n$ 行第 $m$ 列的整数。如果 $m=n$，这个整数将会是 $0$。

输出一行一个整数，表示满足条件的细菌序列的最小长度。

#### 【数据范围】 对于 $100\%$ 的数据，保证 $1 \le K \le 9$。 #### 【说明】 本题分值按 COCI 原题设置，满分 $160$。 题目译自 **[COCI2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)** ___T6 MARS___。