题目描述

有 $2^N$ 个人，编号为 $1$ 到 $2^N$，将参加一场猜拳比赛。

比赛的进行如下：

• 参与者按照从左到右的顺序排成一行，依次是 Person $1$、Person $2$、$\\ldots$、Person $2^N$。
• 设 $2M$ 为当前行的长度。对于每个 $i\\ (1\\leq i \\leq M)$，从左边数第 $(2i-1)$ 个和第 $(2i)$ 个人进行一场比赛。然后，输掉比赛的 $M$ 个人将从行中移除。这个过程重复 $N$ 次。

在这里，如果第 $i$ 个人恰好赢得了 $j$ 场比赛，他们将获得 $C_{i,j}$ 日元（日本货币）。赢得零场比赛的人将不会获得任何奖金。在比赛结果可以自由操纵的情况下，找出 $2^N$ 个人可能获得的总奖金的最大可能值。

约束条件

• $1 \\leq N \\leq 16$
• $1 \\leq C_{i,j} \\leq 10^9$
• 输入中的所有值都是整数。

输入格式

输入以标准输入给出，格式如下：

$N$ $C_{1,1}$ $C_{1,2}$ $\\ldots$ $C_{1,N}$ $C_{2,1}$ $C_{2,2}$ $\\ldots$ $C_{2,N}$ $\\vdots$ $C_{2^N,1}$ $C_{2^N,2}$ $\\ldots$ $C_{2^N,N}$

输出格式

输出答案。

示例输入 1

2
2 5
6 5
2 1
7 9

示例输出 1

15

参与者初始的行为 $(1,2,3,4)$。

如果 Person $2$ 在和 Person $1$ 的比赛中获胜，Person $4$ 在和 Person $3$ 的比赛中获胜，那么行变为 $(2,4)$。

然后，如果 Person $4$ 在和 Person $2$ 的比赛中获胜，行变为 $(4)$，比赛结束。

在这里，Person $2$ 恰好赢得了 $1$ 场比赛，Person $4$ 恰好赢得了 $2$ 场比赛，所以他们总共获得 $0+6+0+9=15$ 日元，这是最大可能的总和。

示例输入 2

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

示例输出 2

4