← 返回题目列表

AtCoder · abc263_f

I. 锦标赛

中文机器翻译题面 查看原题

分数: 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