Spices

题目描述

商店 supaisu-ya 销售着 $2^N-1$ 种香料：香料 $1$、香料 $2$、$\ldots$、香料 $2^N-1$。每种香料各有一包库存。 对于每个 $i = 1, 2, \ldots, 2^N-1$，香料 $i$ 的价格为 $c_i$ 日元。 Takahashi 可以购买这些香料中的任意若干种。 他计划回家后通过选择一项或多项买来的香料并将它们混合来做咖喱。
如果将 $k$ 种香料，香料 $A_1$、香料 $A_2$、$\ldots$、香料 $A_k$ 混合，得到的咖喱的辣度是 $A_1 \oplus A_2 \oplus \cdots \oplus A_k$，其中 $\oplus$ 表示按位异或。 Takahashi 想在回家后根据自己的感觉来决定咖喱的辣度。目前，他会购买一组香料，使他能够做出从 $1$ 到 $2^N-1$ 的任意辣度的咖喱。输出 Takahashi 支付的最少可能金额。

输入格式

输入按下列格式从标准输入给出： $N$ $c_1$ $c_2$ $\ldots$ $c_{2^N-1}$

输出格式

输出 Takahashi 支付的最少可能金额。

2
4 5 3

7

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

15

提示

$2 \leq N \leq 16$ $1 \leq c_i \leq 10^9$ 输入中的所有值均为整数。如果 Takahashi 购买了香料 $1$ 和 $3$，他可以按照如下方式做出任意从 $1$ 到 $3$ 的辣度的咖喱。

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

在这里，Takahashi 支付 $c_1 + c_3 = 4 + 3 = 7$ 日元，这是他所支付的最少可能金额。

标签: AtCoder|abc236F

来源

AtCoder|abc236F