配点 : $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}$

出力

高橋君が支払う金額としてあり得る最小値を出力せよ。

2
4 5 3

7

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

• 辛さ $1$ のカレーを作るには、スパイス $1$ のみを使い、
• 辛さ $2$ のカレーを作るには、スパイス $1$ とスパイス $3$ を組み合わせ、
• 辛さ $3$ のカレーを作るには、スパイス $3$ のみを使えば良いです。

このとき高橋君が支払う金額は $c_1 + c_3 = 4 + 3 = 7$ 円であり、これが高橋君が支払う金額としてあり得る最小値です。

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

15