科学家们在火星上发现了一些奇怪的细菌，目前正忙于研究它们。他们注意到细菌的数量是 2 的幂，因为火星上的每个细菌都会分裂成两个新细菌（在此过程中原本的细菌会死亡），且这一切都是从单个细菌开始的。

因此，第一代只有一个细菌。它分裂成第二代的两个细菌，接着分裂成第三代的四个细菌，依此类推——直到科学家们发现的第 $K+1$ 代的 $2^K$ 个细菌。他们用 $1$ 到 $2^K$ 的数字按以下方式对这些细菌进行了编号：

• 前一代（第 $K$ 代）细菌的后代依次为：$\{1, 2\}, \{3, 4\}, \{5, 6\}, \dots, \{2^K - 1, 2^K\}$
• 更早一代（第 $K-1$ 代）细菌的后代依次为：$\{1, 2, 3, 4\}, \{5, 6, 7, 8\}, \dots, \{2^K - 3, 2^K - 2, 2^K - 1, 2^K\}$
• 再早一代（第 $K-2$ 代）细菌的后代依次为：$\{1, 2, 3, 4, 5, 6, 7, 8\}, \dots, \{2^K - 7, 2^K - 6, 2^K - 5, 2^K - 4, 2^K - 3, 2^K - 2, 2^K - 1, 2^K\}$
• ...
• 第二代两个细菌的后代依次为：$\{1, 2, \dots, 2^{K-1}\}$ 和 $\{2^{K-1} + 1, 2^{K-1} + 2, \dots, 2^K\}$

其中花括号表示单个细菌的后代集合。也就是说，当前这一代（第 $K+1$ 代）的 $2^K$ 个细菌的编号方式使得任何祖先细菌的后代都具有连续的编号。

请注意，存在许多不同的细菌排列方式，它们仍然满足“任何祖先细菌的后代在序列中都处于连续位置”的规则。科学家们希望将这些细菌排成一个满足该规则且长度尽可能小的序列。细菌序列的长度定义为序列中所有相邻细菌对之间的距离之和。

具体来说，每两个细菌之间存在某种可量化的排斥力，如果它们在序列中相邻，该排斥力即为它们之间的最小距离。（排斥力在序列中不相邻的细菌之间不起作用。）给定所有细菌对之间的排斥力值，求满足上述后代规则的细菌序列（排列）的最小可能长度。

输入格式

输入的第一行包含问题描述中的正整数 $K$ ($1 \le K \le 9$)。

接下来的 $2^K$ 行，每行包含 $2^K$ 个介于 $[0, 10^6]$ 之间的整数。这 $2^K \times 2^K$ 个数字表示细菌对之间的排斥力：第 $m$ 行第 $n$ 列的数字是细菌 $m$ 和 $n$ 之间的排斥力。显然，该数值将等于第 $n$ 行第 $m$ 列的数值。当 $m = n$ 时，数值为 $0$。

输出格式

输出的第一行也是唯一一行应当包含满足约束条件的细菌序列的最小可能长度。

样例

输入样例 1

2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

输出样例 1

13

输入样例 2

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

输出样例 2

32