锦标赛

题目描述

编号为 $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$、人 $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}$

输出格式

输出答案。

样例

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

数据范围

• $1 \leq N \leq 16$
• $1 \leq C_{i,j} \leq 10^9$
• 所有输入都是整数。