시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 6 6 100.000%

문제

You have a set S of n elements. You want to paint each subset of S either red or blue. For each subset s of S, you know that the cost to paint it red is Rs, and the cost to paint it blue is Bs.

Note: you want to paint subsets, not the elements.

There is only one requirement:

  • If a and b are two subsets of S of the same color, the subset a ∪ b has the same color as a and b.

Find the minimum total cost to paint all 2n subsets.

입력

The first line contains a single integer n (0 ≤ n ≤ 20), the number of elements.

The second line contains 2n integers R0, R1, . . . , R2n−1 (−109 ≤ Ri ≤ 109), the costs to paint subsets red.

The third line contains 2n integers B0, B1, . . . , B2n−1 (−109 ≤ Bi ≤ 109), the costs to paint subsets blue.

The subset i (0 ≤ i < 2n) is a subset consisting of elements j such that the j-th bit in the binary representation of i is 1.

출력

Print one integer: the minimum cost to paint all subsets.

예제 입력 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