在数学锦标赛中，共有 $2^n$ 名数学家，每人都有一个初始声望值 $a_i$，该值可能是负数。当两名数学家之间进行“数学决斗”时，组织者会以一种仅他们自己知道的方式决定胜者。败者的声望保持不变，而胜者的声望会增加败者的声望（$a[i] += a[j]$）。注意，这甚至可能导致胜者的声望下降！

锦标赛共包含 $n$ 个阶段。在每个阶段，组织者会将参赛者两两配对。在每一对中进行一场数学决斗，胜者晋级下一阶段，败者被淘汰。第一阶段结束后，剩余 $2^{n-1}$ 名参赛者；第二阶段结束后，剩余 $2^{n-2}$ 名参赛者，以此类推。最终，在第 $n$ 个阶段结束后，仅剩一名参赛者，并被授予一块象征性的巧克力。

锦标赛结束后，计划对其中一名参赛者进行采访，该参赛者不一定是获得巧克力的那一位。采访的最佳人选是 $2^n$ 名数学家中最终声望最高的那一位。锦标赛的声望以及吸引明年赞助商的可能性都取决于这次采访。请帮助组织者在每个阶段对参赛者进行配对并选出胜者，以使其中一名数学家的最终声望最大化。求出这个最大值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 16$)。

第二行包含 $2^n$ 个整数 $a_1, a_2, \dots, a_{2^n}$。其中第 $i$ 个数是第 $i$ 位参赛者的初始声望 ($-10^6 \le a_i \le 10^6$)。

输出格式

输出一个整数，表示锦标赛结束后 $2^n$ 名数学家中可能达到的最高声望值。

样例

输入 1

2
5 -1 2 -10

输出 1

7

说明

在第一阶段，组织者可以进行如下配对（这不一定是唯一的最佳选择）：

• 在声望为 ($a_1 = 5, a_3 = 2$) 的配对中，让数学家 3 获胜；他的声望从 2 变为 $2+5 = 7$。参赛者 1 被淘汰，声望为 5。
• 在配对 ($a_2 = -1, a_4 = -10$) 中，让数学家 2 获胜；他的声望从 $-1$ 变为 $-1 + (-10) = -11$。参赛者 4 被淘汰，声望为 $-10$。

在这种情况下，声望为 7 和 $-11$ 的数学家晋级到第二阶段。组织者选择后者作为胜者；他们的声望从 $-11$ 变为 $-11 + 7 = -4$。参赛者 3 被淘汰，声望为 7，参赛者 2 获得巧克力，最终声望为 $-4$。

四名数学家的最终声望分别为 $5, -4, 7, -10$。最高声望为 7，这是可能达到的最大值。