You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

超市中有 $2^k-1$ 种食材，分别标号为 $1,2,\cdots 2^k-1$，其中购买第 $i$ 种食材需要花费 $c_i$。

小 Z 需要购买其中的一些食材来满足当天的烹饪需求，具体地，他要求每个 $1,2,\cdots 2^k-1$ 中的数 $m$，都可以选择一些购买过的食材，使得这些食材编号的异或和为 $m$。更详细的解释可以参看样例解释 1。

小 Z 想知道他至少需要花费多少才能满足他的要求。

输入格式

第一行包含一个正整数 $k$。

第二行包含 $2^k-1$ 个正整数 $c_i$，含义如上。

输出格式

输出一行一个正整数表示答案。

样例 #1

样例输入 #1

3
3 2 4 7 1 5 8

样例输出 #1

6

提示

样例解释 1

可以购买编号为 $1,2,5$ 的三种食材，共花费 $6$，这样：

即可表示出所有 $1,2,\cdots 7$ 中的数。

样例输入/输出 2

详见下发文件下的 ex_recipe2.in/out。

ex_recipe1.in
ex_recipe1.out
ex_recipe2.in
ex_recipe2.out

这个数据满足第 $3\sim 5$ 个测试点的限制。

数据规模与约定

对所有数据，保证 $1\le k\le 18,1\le c_i\le 10^9$。