AtCoder 품질 문제

집합 $S$의 원소는 $n$개 있다. $S$의 각 부분집합을 빨간색 또는 파란색으로 칠하려고 한다. 부분집합 $s$를 빨간색으로 칠하는 비용은 $R_s$이고, 파란색으로 칠하는 비용은 $B_s$이다.

참고로 칠하는 대상은 원소가 아니라 부분집합이다.

조건은 하나뿐이다.

• $a$와 $b$가 같은 색의 부분집합이면, 부분집합 $a \cup b$는 $a$, $b$와 같은 색이다.

$2^n$개의 부분집합을 모두 칠할 때 필요한 최소 총비용을 구하라.

첫째 줄에 원소의 개수 $n$ ($0 \le n \le 20$)이 정수 하나로 주어진다.

둘째 줄에는 부분집합을 빨간색으로 칠하는 비용 $R_0, R_1, \ldots, R_{2^n-1}$ ($-10^9 \le R_i \le 10^9$)이 정수 $2^n$개로 주어진다.

셋째 줄에는 부분집합을 파란색으로 칠하는 비용 $B_0, B_1, \ldots, B_{2^n-1}$ ($-10^9 \le B_i \le 10^9$)이 정수 $2^n$개로 주어진다.

부분집합 $i$ ($0 \le i < 2^n$)는 $i$를 이진수로 나타냈을 때 $j$번째 비트가 1인 원소 $j$로 이루어진 집합이다.

모든 부분집합을 칠하는 데 드는 최소 총비용을 정수 하나로 출력한다.