分数: 500 点
问题陈述
2^N 人,已编号 1 to 2^N,将参加石头剪刀布锦标赛。
比赛进行如下:
- 参与者按人的顺序排列成一排 1, 人 2, \ldots, 人 2^N 从左到右。
- 让 2M 是行的当前长度。对于每个 i\ (1\leq i \leq M), (2i-1)-th 和 自记录开始以来,第 (2i)左边第 1 个人互相玩游戏。然后, 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).
如果人 2 赢得与 Person 的比赛 1和人 4 赢得与 Person 的比赛 3,该行变为 (2,4).
那么,如果人 4 赢得与 Person 的比赛 2,该行变为 (4),比赛结束。
在这里,人 2 完全获胜 1 游戏和人 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