题目描述

题目译自 Open Olympiad in Informatics 2024 Day2 T2 「Три массива / Three Arrays」。

给定三个长度为 $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 \leq n \leq 100000)$，表示数组 $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})$。

输出格式

输出一个整数，即通过构建数组 $A$ 和 $B$ 可以获得的最大 $A_{n} + B_{n}$ 值。

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

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. 对 $B_{5}$ 应用最小值操作：$A_{5} = 11$ 保持不变，$B_{5} = \min(B_{5}, R_{5}) = \min(27, 23) = 23$。
12. $A_{5} + B_{5} = 11 + 23 = 34$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。