AtCoder Quality Problem

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$, the cost to paint it red is $R_s$, and the cost to paint it blue is $B_s$.

Note: you paint subsets, not the elements.

There is one requirement:

• If $a$ and $b$ are two subsets of the same color, then the subset $a \cup b$ has the same color as $a$ and $b$.

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

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

The second line contains $2^n$ integers $R_0, R_1, \ldots, R_{2^n-1}$ ($-10^9 \le R_i \le 10^9$), the costs to paint subsets red.

The third line contains $2^n$ integers $B_0, B_1, \ldots, B_{2^n-1}$ ($-10^9 \le B_i \le 10^9$), the costs to paint subsets blue.

Subset $i$ ($0 \le i < 2^n$) consists of the elements $j$ for which the $j$-th bit in the binary representation of $i$ is 1.

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