問題文

スパイス屋には、スパイス $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