AT_abc236_f [ABC236F] Spices

题目描述

在香料店里，有 $2^N-1$ 种香料，分别为香料 $1$、香料 $2$、$\ldots$、香料 $2^N-1$，每种香料各有 $1$ 个出售。对于 $i=1,2,\ldots,2^N-1$，香料 $i$ 的价格为 $c_i$ 日元。高桥君可以任意购买这些香料。

高桥君回家后，会从买到的香料中选择至少 $1$ 种，将它们组合做成咖喱。
如果高桥君组合了香料 $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}$

输出格式

请输出高桥君可能需要支付的最小金额。

输入输出样例 #1

输入 #1

2
4 5 3

输出 #1

7

输入输出样例 #2

输入 #2

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

输出 #2

15

说明/提示

限制条件

• $2 \leq N \leq 16$
• $1 \leq c_i \leq 10^9$
• 输入均为整数

样例解释 1

如果高桥君购买香料 $1$ 和香料 $3$，则可以如下方式做出辣度为 $1$ 到 $3$ 的任意整数的咖喱：

• 要做辣度为 $1$ 的咖喱，只需使用香料 $1$；
• 要做辣度为 $2$ 的咖喱，组合香料 $1$ 和香料 $3$；
• 要做辣度为 $3$ 的咖喱，只需使用香料 $3$。

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

由 ChatGPT 4.1 翻译