102635: [AtCoder]ABC263 F - Tournament

Problem Statement

$2^N$ people, numbered $1$ to $2^N$, will participate in a rock-paper-scissors tournament.

The tournament proceeds as follows:

• The participants are arranged in a row in the order Person $1$, Person $2$, $\ldots$, Person $2^N$ from left to right.
• Let $2M$ be the current length of the row. For each $i\ (1\leq i \leq M)$, the $(2i-1)$-th and $(2i)$-th persons from the left play a game against each other. Then, the $M$ losers are removed from the row. This process is repeated $N$ times.

Here, if Person $i$ wins exactly $j$ games, they receive $C_{i,j}$ yen (Japanese currency). A person winning zero games receives nothing. Find the maximum possible total amount of money received by the $2^N$ people if the results of all games can be manipulated freely.

Constraints

• $1 \leq N \leq 16$
• $1 \leq C_{i,j} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print the answer.

Sample Input 1

2
2 5
6 5
2 1
7 9

Sample Output 1

15

The initial row of the people is $(1,2,3,4)$.

If Person $2$ wins the game against Person $1$, and Person $4$ wins the game against Person $3$, the row becomes $(2,4)$.

Then, if Person $4$ wins the game against Person $2$, the row becomes $(4)$, and the tournament ends.

Here, Person $2$ wins exactly $1$ game, and Person $4$ wins exactly $2$ games, so they receive $0+6+0+9=15$ yen in total, which is the maximum possible sum.

Sample Input 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

Sample Output 2

4

问题描述

编号为1到2^N的2^N个人将参加一个猜拳比赛。

比赛进行如下：

• 参赛者按照从左到右的顺序排列为Person 1, Person 2, ..., Person 2^N。
• 当前行的长度为2M。对于每个i\ (1≤i≤M)$，从左数第(2i-1)$和第(2i)$个人进行比赛。然后，将M个输家从行中移除。这个过程重复N次。

如果Person $i$恰好赢了j场比赛，他们将获得$C_{i,j}$日元（日本货币）。赢得零场比赛的人将一无所获。如果所有比赛的结果都可以自由操纵，请找出这2^N人获得的最大可能总金额。

限制条件

• $1≤N≤16$
• $1≤C_{i,j}≤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