← 返回题目列表

AtCoder · abc236_f

I. 香料

中文机器翻译题面 查看原题

分数: 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