최대 유량

Bobo에게는 $(2n + 2)$개의 정점을 가진 무방향 그래프가 있고, 정점에는 다음과 같은 정수 쌍이 붙어 있다: $(0, 0), (0, 1), \dots, (0, n), (1, 0), (1, 1), \dots, (1, n)$. 그래프의 간선은 세 종류다.

• 첫 번째 종류의 간선은 $i \in \{1, 2, \dots, n\}$에 대해 정점 $(0, i - 1)$과 $(0, i)$를 용량 $a_i$로 연결한다.
• 두 번째 종류의 간선은 $i \in \{1, 2, \dots, n\}$에 대해 정점 $(1, i - 1)$과 $(1, i)$를 용량 $b_i$로 연결한다.
• 세 번째 종류의 간선은 $i \in \{1, 2, \dots, 2n + 1\}$에 대해 정점 $(0, \lfloor\frac{i - 1}{2} \rfloor)$과 $(1, \lfloor \frac{i}{2}\rfloor)$를 용량 $c_i$로 연결한다.

Bobo는 정점 $(0, 0)$에서 정점 $(1, n)$으로 가는 최대 유량을 구하려 한다.

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝에서 종료된다. 각 테스트 케이스에 대해:

첫째 줄에는 정수 $n$이 주어진다 ($1 \leq n \leq 5 \cdot 10^5$).

둘째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어진다.

셋째 줄에는 $n$개의 정수 $b_1, b_2, \dots, b_n$이 주어진다.

넷째 줄에는 $(2n + 1)$개의 정수 $c_1, c_2, \dots, c_{2n + 1}$이 주어진다.

제약은 $1 \leq a_i, b_i, c_i \leq 10^9$이다.

테스트 케이스의 수는 $10^5$을 넘지 않고, 모든 $n$의 합은 $5 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 최대 유량을 나타내는 정수를 한 줄에 출력한다.