题目描述

科学家在火星上发现了一些奇怪的细菌，正在研究它们。他们注意到细菌的数量是 $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$。

输出格式

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

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

提示

【数据范围】

对于 $100\%$ 的数据，保证 $1 \le K \le 9$。

【说明】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 COCI2012-2013 CONTEST #1 T6 MARS。