分数: 500 点
问题陈述
商店supaisu-ya有卖 2^N-1 香料种类: 香料 1,香料 2, \ldots,香料 2^N-1。每种香料都有一包库存。 对于每个 i = 1, 2, \ldots, 2^N-1,香料 i 成本 c_i 日元。 高桥可以购买任何这些香料。
他计划回家后选择一种或多种购买的香料并将其混合来制作咖喱。
If 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}
输出
打印高桥支付的最低可能金额。
示例输入 1
2 4 5 3
示例输出 1
7
如果高桥购买Spice 1 和 3,他可以制作任何辣度的咖喱 1 通过 3,如下。
- 制作辣味咖喱 1,仅使用 Spice 1.
- 制作辣味咖喱 2,混合香料 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