香料

题目描述

香料店「スパイス屋」出售 $2^N-1$ 种香料：香料 $1$、香料 $2$、$\ldots$、香料 $2^N-1$。每种香料都有 $1$ 包库存。 对于每个 $i = 1, 2, \ldots, 2^N-1$，香料 $i$ 的价格为 $c_i$ 日元。 高桥可以购买其中任意多种香料。

他计划回家后从购买的香料中选择一种或多种混合制作咖喱。

若将香料 $A_1$、香料 $A_2$、$\ldots$、香料 $A_k$ 这 $k$ 种香料混合，制成的咖喱的辣度为 $A_1 \oplus A_2 \oplus \cdots \oplus A_k$，其中 $\oplus$ 表示按位异或。

高桥想回家后根据自己的感觉来决定咖喱的辣度。因此，现在他会购买一组香料，使得能够做出从 $1$ 到 $2^N-1$ 任意辣度的咖喱。请输出高桥需要支付的最小金额。

输入格式

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

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

输出格式

输出高桥需要支付的最小金额。

样例

2
4 5 3

7

若高桥购买香料 $1$ 和香料 $3$，则可以做出从 $1$ 到 $3$ 任意辣度的咖喱，如下所示。

要做出辣度为 $1$ 的咖喱，只使用香料 $1$。

要做出辣度为 $2$ 的咖喱，混合香料 $1$ 和香料 $3$。

要做出辣度为 $3$ 的咖喱，只使用香料 $3$。

此时，高桥支付 $c_1 + c_3 = 4 + 3 = 7$ 日元，这是他需要支付的最小金额。

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

15

数据范围

• $2 \le N \le 16$
• $1 \le c_i \le 10^9$
• 输入中的所有值均为整数。