题目描述

商店 supaisu-ya 销售 $2^N-1$ 种香料：Spice $1$、Spice $2$、$\ldots$、Spice $2^N-1$。每种香料都有一包备货。对于每个 $i = 1, 2, \ldots, 2^N-1$，Spice $i$ 的价格为 $c_i$ 日元。高桥可以购买其中任意一种香料。

他计划回家后用购买的香料来做咖喱。如果混合了 $k$ 种香料，即 Spice $A_1$、Spice $A_2$、$\ldots$、Spice $A_k$，所得咖喱的辣度为 $A_1 \\oplus A_2 \\oplus \\cdots \\oplus A_k$，其中 $\\oplus$ 表示按位异或。

高桥想根据回家后的感觉来决定咖喱的辣度。现在，他要购买一组能够制作出辣度从 $1$ 到 $2^N-1$ 的咖喱的香料。请打印高桥最少需要支付的金额。

约束条件

• $2 \\leq N \\leq 16$
• $1 \\leq c_i \\leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $c_1$ $c_2$ $\\ldots$ $c_{2^N-1}$

输出

打印高桥最少需要支付的金额。

示例输入 1

2
4 5 3

示例输出 1

7

如果高桥购买了 Spice $1$ 和 $3$，他可以制作出辣度从 $1$ 到 $3$ 的咖喱，具体如下：

• 要制作辣度为 $1$ 的咖喱，只需使用 Spice $1$。
• 要制作辣度为 $2$ 的咖喱，混合使用 Spice $1$ 和 $3$。
• 要制作辣度为 $3$ 的咖喱，只需使用 Spice $3$。

在这种情况下，高桥需要支付 $c_1 + c_3 = 4 + 3 = 7$ 日元，这是他最少需要支付的金额。

示例输入 2

4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

示例输出 2

15