题目描述

给定三个长度为 $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

数据范围与提示

详细子任务附加限制及分值如下表所示：