Bobo 有一个无向图，包含 $(2n + 2)$ 个顶点，这些顶点用以下整数对标记：$(0, 0), (0, 1), \dots, (0, n), (1, 0), (1, 1), \dots, (1, 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, n\}$。
• 第三类边连接顶点 $(0, \lfloor \frac{i-1}{2} \rfloor)$ 和 $(1, \lfloor \frac{i}{2} \rfloor)$，容量为 $c_i$，其中 $i \in \{1, 2, \dots, 2n + 1\}$。

Bobo 想要找到从顶点 $(0, 0)$ 到顶点 $(1, n)$ 的最大流。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 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 \le a_i, b_i, c_i \le 10^9$。 保证测试用例数量不超过 $10^5$，且所有 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示最大流。

样例

输入 1

1
2
2
1 3 1
3
1 4 7
2 5 8
2 3 3 2 1 2 4

输出 1

5
6