题目描述

$1$ から $2^N$ の番号がついた $2^N$ 人でじゃんけん大会を行います。

大会は以下の形式で行われます。

• 参加者を人 $1$、人 $2$、 $\ldots$、人 $2^N$ の順に横一列に並べる。
• 現在の列の長さを $2M$ として、各 $i\ (1\leq\ i\ \leq\ M)$ について左から $2i-1$ 番目の人と左から $2i$ 番目の人で試合を行い、負けた $M$ 人を列から外す。これを $N$ 回繰り返す。

ここで、人 $i$ はちょうど $j$ 回試合に勝つと $C_{i,j}$ 円獲得できます。$1$ 回も勝たなかった場合は何も貰えません。全ての試合の勝敗を自由に決められるとき、人 $1$、人 $2$、 $\ldots$、人 $2^N$ が貰えるお金の合計の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定 $n$，存在 $2^n$ 个人站成一排进行比赛，比赛赛制按照类满二叉树进行，即每 $2i$ 和 $2i - 1$ 两人进行比赛，胜利者进入下一层继续按照相同赛制比赛，直至最终剩余一人。若第 $i$ 人获得了 $j$ 场比赛的胜利，那么将获得 $C_{i, j}$ 的奖金。你可以任意安排每场比赛的输赢，以最大化所有人的奖金和，求最大值。

2
2 5
6 5
2 1
7 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

提示

制約

• $1\ \leq\ N\ \leq\ 16$
• $1\ \leq\ C_{i,j}\ \leq\ 10^9$
• 入力は全て整数

Sample Explanation 1

初めの列は $(1,2,3,4)$ です。 人 $1$ と人 $2$ の試合で人 $2$ が勝ち、人 $3$ と人 $4$ の試合で人 $4$ が勝ったとすると、列は $(2,4)$ になります。 次に人 $2$ と人 $4$ の試合で人 $4$ が勝ったとすると、列は $(4)$ になり、これで大会が終了となります。 このとき、人 $2$ はちょうど $1$ 回勝ち、人 $4$ はちょうど $2$ 回勝ったので、貰えるお金の合計は $0+6+0+9=15$ となります。 これが貰えるお金の合計の最大値です。