给你三个长度为 $n$ 的数组 $D$、$L$ 和 $R$，其元素下标从 $1$ 开始，以及整数 $a_0$ 和 $b_0$。你将根据以下规则构造两个长度为 $n + 1$ 的数组 $A$ 和 $B$：

1. $A_0 = a_0$，$B_0 = b_0$

2. 对于从 $1$ 到 $n$ 的所有 $i$，执行以下操作：

   • 令 $A_i = A_{i-1} + D_i$ 且 $B_i = B_{i-1} + D_i$。

   • 选择以下操作中的恰好一个并执行：

     • $A_i = \min(A_i, L_i)$
     • $B_i = \min(B_i, R_i)$

你想构造数组 $A$ 和 $B$ 以最大化 $A_n + B_n$ 的值。求通过执行上述操作可以得到的 $A_n + B_n$ 的最大值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$) —— 数组 $D$、$L$ 和 $R$ 的长度。

第二行包含 $n$ 个整数 $D_1, D_2, \dots, D_n$ ($0 \le D_i \le 10^9$) —— 数组 $D$。

第三行包含 $n$ 个整数 $L_1, L_2, \dots, L_n$ ($0 \le L_i \le 10^9$) —— 数组 $L$。

第四行包含 $n$ 个整数 $R_1, R_2, \dots, R_n$ ($0 \le R_i \le 10^9$) —— 数组 $R$。

第五行包含两个整数 $a_0$ 和 $b_0$ ($0 \le a_0, b_0 \le 10^9$)。

输出格式

输出一个整数 —— 在所有可能的构造数组 $A$ 和 $B$ 的方法中，$A_n + B_n$ 的最大可能值。

子任务

本题的测试点分为六个子任务。只有当通过该子任务的所有测试点以及所有要求的子任务的测试点时，才能获得该子任务的分数。请注意，某些子任务不要求通过样例测试。非正式评测（Offline-evaluation）意味着该子任务的评测结果将在比赛结束后才会公布。

样例

输入格式 1

5
4 0 7 0 8
10 5 3 7 7
8 5 9 2 23
4 8

输出格式 1

34

说明

在第一组样例数据中，以下操作顺序可以得到最大答案：

1. $A_0 = 4$，$B_0 = 8$。
2. $A_1 = A_0 + D_1 = 4 + 4 = 8$，$B_1 = B_0 + D_1 = 8 + 4 = 12$。
3. 对 $A_1$ 取最小值：$A_1 = \min(A_1, L_1) = \min(10, 8) = 8$，$B_1 = 12$ 的值保持不变。
4. $A_2 = A_1 + D_2 = 8 + 0 = 8$，$B_2 = B_1 + D_2 = 12 + 0 = 12$。
5. 对 $A_2$ 取最小值：$A_2 = \min(A_2, L_2) = \min(5, 8) = 5$，$B_2 = 12$ 的值保持不变。
6. $A_3 = A_2 + D_3 = 12$，$B_3 = B_2 + D_3 = 19$。
7. 对 $A_3$ 取最小值：$A_3 = \min(A_3, L_3) = 3$，$B_3 = 19$ 的值保持不变。
8. $A_4 = A_3 + D_4 = 3$，$B_4 = B_3 + D_4 = 19$。
9. 对 $A_4$ 取最小值：$A_4 = \min(A_4, L_4) = 3$，$B_4 = 19$ 的值保持不变。
10. $A_5 = A_4 + D_5 = 11$，$B_5 = B_4 + D_5 = 27$。
11. $A_5 = 11$ 的值保持不变，对 $B_5$ 取最小值：$B_5 = \min(B_5, R_5) = \min(27, 23) = 23$。
12. $A_5 + B_5 = 11 + 23 = 34$。

可以证明这就是最大值。