当前没有测试数据。

F - 锦标赛

分数：500分

问题描述

有$2^N$个人，编号为$1$到$2^N$，将参加一场剪刀石头布锦标赛。

锦标赛的进行步骤如下：

• 参赛者按照从左到右的顺序排列在一行中，顺序为人员$1$，人员$2$，$\ldots$，人员$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}$

输出

输出答案。

2
2 5
6 5
2 1
7 9

15

参赛人员的初始排列为$(1,2,3,4)$。

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

然后，如果人员$4$在与人员$2$的比赛中获胜，行变为$(4)$，锦标赛结束。

在这里，人员$2$赢得了$1$场比赛，人员$4$赢得了$2$场比赛，因此他们总共获得了$0+6+0+9=15$日元，这是可能的最大总和。

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

4