Description

你有三个长度为 $n$ 的数组 $D$、$L$ 和 $R$，下标从 $1$ 开始。同时给定整数 $a_{0}$ 和 $b_{0}$。你需要按如下规则构造两个长度为 $n+1$ 的数组 $A$ 和 $B$：

• $A_{0} = a_{0}$，$B_{0} = b_{0}$
• 对于所有 $1 \leq i \leq n$，依次进行以下操作：
  • 令 $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}$ 的最大值。

Input Format

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$），表示数组 $D$、$L$ 和 $R$ 的长度。

第二行包含 $n$ 个整数 $D_{1}, D_{2}, \ldots, D_{n}$（$0 \leq D_{i} \leq 10^{9}$），表示数组 $D$。

第三行包含 $n$ 个整数 $L_{1}, L_{2}, \ldots, L_{n}$（$0 \leq L_{i} \leq 10^{9}$），表示数组 $L$。

第四行包含 $n$ 个整数 $R_{1}, R_{2}, \ldots, R_{n}$（$0 \leq R_{i} \leq 10^{9}$），表示数组 $R$。

第五行包含两个整数 $a_{0}$ 和 $b_{0}$（$0 \leq a_{0}, b_{0} \leq 10^{9}$）。

Output Format

输出一个整数，表示所有可能方案中 $A_{n} + B_{n}$ 的最大值。

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

34

Hint

说明

在第一个输入样例中，以下操作顺序可以得到最大答案：

• $A_{0} = 4$，$B_{0} = 8$。
• $A_{1} = A_{0} + D_{1} = 4 + 4 = 8$，$B_{1} = B_{0} + D_{1} = 8 + 4 = 12$。
• 对 $A_{1}$ 应用 $\min$，$A_{1} = \min(8, 10) = 8$，$B_{1} = 12$ 不变。
• $A_{2} = A_{1} + D_{2} = 8 + 0 = 8$，$B_{2} = B_{1} + D_{2} = 12 + 0 = 12$。
• 对 $A_{2}$ 应用 $\min$，$A_{2} = \min(8, 5) = 5$，$B_{2} = 12$ 不变。
• $A_{3} = A_{2} + D_{3} = 5 + 7 = 12$，$B_{3} = B_{2} + D_{3} = 12 + 7 = 19$。
• 对 $A_{3}$ 应用 $\min$，$A_{3} = \min(12, 3) = 3$，$B_{3} = 19$ 不变。
• $A_{4} = A_{3} + D_{4} = 3 + 0 = 3$，$B_{4} = B_{3} + D_{4} = 19 + 0 = 19$。
• 对 $A_{4}$ 应用 $\min$，$A_{4} = \min(3, 7) = 3$，$B_{4} = 19$ 不变。
• $A_{5} = A_{4} + D_{5} = 3 + 8 = 11$，$B_{5} = B_{4} + D_{5} = 19 + 8 = 27$。
• 对 $B_{5}$ 应用 $\min$，$A_{5} = 11$，$B_{5} = \min(27, 23) = 23$。
• $A_{5} + B_{5} = 11 + 23 = 34$。

可以证明这是最大值。

计分方式

本题共六组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。Offline-evaluation 表示该组结果仅在赛后可见。

翻译由 ChatGPT-4.1 完成。