题目描述

スパイス屋には、スパイス $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$ 以下の任意の整数の辛さのカレーを作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

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

题目大意

有 $2 ^ N - 1$ 个数字，分别编号为 $1, 2, \dots, 2 ^ N - 1$，想获得编号为 $i$ 的数字需要支付 $c_i$ 的代价。

现在你可以从这些数字中选出一些数，使得你可以通过你选择的某些数的编号的异或和来表示出 $[1, 2 ^ N - 1]$ 中的所有数。

请你求出最少需要支付多少代价。

2
4 5 3

7

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

15

提示

制約

• $2\ \leq\ N\ \leq\ 16$
• $1\ \leq\ c_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

高橋君がスパイス $1$ とスパイス $3$ を買うと、下記の通り、$1$ 以上 $3$ 以下の任意の整数の辛さのカレーを作ることができます。 - 辛さ $1$ のカレーを作るには、スパイス $1$ のみを使い、 - 辛さ $2$ のカレーを作るには、スパイス $1$ とスパイス $3$ を組み合わせ、 - 辛さ $3$ のカレーを作るには、スパイス $3$ のみを使えば良いです。 このとき高橋君が支払う金額は $c_1\ +\ c_3\ =\ 4\ +\ 3\ =\ 7$ 円であり、これが高橋君が支払う金額としてあり得る最小値です。