/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
スパイス屋には、スパイス 1 、スパイス 2、\ldots 、スパイス 2^N-1 の 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 以下の任意の整数の辛さのカレーを作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してください。
制約
- 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