配点 : $500$ 点

問題文

$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$ が貰えるお金の合計の最大値を求めてください。

制約

• $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)$ です。

人 $1$ と人 $2$ の試合で人 $2$ が勝ち、人 $3$ と人 $4$ の試合で人 $4$ が勝ったとすると、列は $(2,4)$ になります。

次に人 $2$ と人 $4$ の試合で人 $4$ が勝ったとすると、列は $(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