你拥有一个包含 $n$ 个元素的集合 $S$。你需要将 $S$ 的每一个子集涂成红色或蓝色。对于 $S$ 的每个子集 $s$，已知将其涂成红色的代价为 $R_s$，将其涂成蓝色的代价为 $B_s$。

注意：你是要给子集涂色，而不是给元素涂色。

题目只有一个要求： * 如果 $a$ 和 $b$ 是两个颜色相同的 $S$ 的子集，那么子集 $a \cup b$ 也必须与 $a$ 和 $b$ 颜色相同。

求将所有 $2^n$ 个子集涂色的最小总代价。

输入格式

第一行包含一个整数 $n$ ($0 \le n \le 20$)，表示元素的个数。 第二行包含 $2^n$ 个整数 $R_0, R_1, \dots, R_{2^n-1}$ ($-10^9 \le R_i \le 10^9$)，表示将各子集涂成红色的代价。 第三行包含 $2^n$ 个整数 $B_0, B_1, \dots, B_{2^n-1}$ ($-10^9 \le B_i \le 10^9$)，表示将各子集涂成蓝色的代价。

子集 $i$ ($0 \le i < 2^n$) 是由那些在 $i$ 的二进制表示中第 $j$ 位为 $1$ 的元素 $j$ 组成的子集。

输出格式

输出一个整数：涂完所有子集的最小总代价。

样例

输入 1

2
-5 9 9 -5
10 -8 -6 3

输出 1

-16

输入 2

3
-15 19 19 -5 30 -3 -16 13
29 -6 -14 -7 24 -5 18 11

输出 2

-22

输入 3

0
-129363358
227605714

输出 3

-129363358

输入 4

1
-120923470 -355154745
-18478014 104068715

输出 4

-476078215

输入 5

3
41 38 35 12 5 15 42 18
37 35 39 13 10 14 11 19

输出 5

173