F - Spices Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

スパイス屋には、スパイス 1 、スパイス 2\ldots 、スパイス 2^N-12^N-1 種類のスパイスがそれぞれ 1 個ずつ売られています。 i = 1, 2, \ldots, 2^N-1 について、スパイス i の値段は c_i 円です。 高橋君はそれらを好きなだけ買うことができます。

高橋君は帰宅後、買ったスパイスのうち 1 つ以上を選び、それらを組み合わせてカレーを作る予定です。
高橋君がスパイス A_1 、スパイス A_2\ldots、スパイス A_kk 個のスパイスを組み合わせると、完成するカレーの辛さは 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

高橋君がスパイス 1 とスパイス 3 を買うと、下記の通り、1 以上 3 以下の任意の整数の辛さのカレーを作ることができます。

  • 辛さ 1 のカレーを作るには、スパイス 1 のみを使い、
  • 辛さ 2 のカレーを作るには、スパイス 1 とスパイス 3 を組み合わせ、
  • 辛さ 3 のカレーを作るには、スパイス 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

Score : 500 points

Problem Statement

The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.

He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.

Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.

Constraints

  • 2 \leq N \leq 16
  • 1 \leq c_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
c_1 c_2 \ldots c_{2^N-1}

Output

Print the minimum possible amount of money Takahashi pays.


Sample Input 1

2
4 5 3

Sample Output 1

7

If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.

  • To make curry of hotness 1, use just Spice 1.
  • To make curry of hotness 2, mix Spice 1 and Spice 3.
  • To make curry of hotness 3, use just Spice 3.

Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.


Sample Input 2

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

Sample Output 2

15