当前没有测试数据。

F - 香料

得分：$500$ 分

问题描述

店铺 supaisu-ya 销售 $2^N-1$ 种香料：香料 $1$, 香料 $2$, $\ldots$, 香料 $2^N-1$。每种香料都有现货。 对于每个 $i = 1, 2, \ldots, 2^N-1$，香料 $i$ 的价格为 $c_i$ 日元。 高橋可以购买任何这些香料。

他计划回家后通过选择一个或多个购买的香料来调制咖喱。
如果调和 $k$ 种香料，即香料 $A_1$, 香料 $A_2$, $\ldots$, 香料 $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}$

输出

打印高橋所支付的最少金额。

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