题目描述

You are given three arrays $D$, $L$, and $R$ of length $n$, with elements indexed from $1$, as well as the integers $a_{0}$ and $b_{0}$. You construct two arrays $A$ and $B$ of length $n+1$ according to the following rules:

• $A_{0} = a_{0}$, $B_{0} = b_{0}$
• For all $i$ from $1$ to $n$, perform the following actions:
  • Set the elements as $A_{i} = A_{i - 1} + D_{i}$ and $B_{i} = B_{i - 1} + D_{i}$.
  • Choose exactly $\textbf{one}$ of the following operations and apply it:
    • $A_{i} = \min(A_{i}, L_{i})$
    • $B_{i} = \min(B_{i}, R_{i})$

You want to construct arrays $A$ and $B$ to maximize the value of $A_{n} + B_{n}$. Find the maximum value of $A_{n} + B_{n}$ that can be obtained by performing the described actions.

输入格式

The first line contains a single integer $n$ ($1 \le n \le 100\,000$) --- the length of arrays $D$, $L$, and $R$.

The second line contains $n$ integers $D_{1},\ D_{2},\ \ldots,\ D_{n}$ ($0 \le D_{i} \le 10^{9}$) --- the array $D$.

The third line contains $n$ integers $L_{1},\ L_{2},\ \ldots,\ L_{n}$ ($0 \le L_{i} \le 10^{9}$) --- the array $L$.

The fourth line contains $n$ integers $R_{1},\ R_{2},\ \ldots,\ R_{n}$ ($0 \le R_{i} \le 10^{9}$) --- the array $R$.

The fifth line contains two integers $a_{0}$ and $b_{0}$ ($0 \le a_{0}, b_{0} \le 10^{9}$).

输出格式

Output a single integer --- the maximum possible value of $A_{n} + B_{n}$ among all possible ways to construct arrays $A$ and $B$.

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

34

提示

Note

In the first set of input data, the following sequence of actions leads to the maximum answer:

• $A_{0} = 4$, $B_{0} = 8$.
• $A_{1} = A_{0} + D_{1} = 4 + 4 = 8$, $B_{1} = B_{0} + D_{1} = 8 + 4 = 12$.
• The minimum is applied to $A_{1} = \min(A_{1}, L_{1}) = \min(10, 8) = 8$, the value of $B_{1} = 12$ remains the same.
• $A_{2} = A_{1} + D_{2} = 8 + 0 = 8$, $B_{2} = B_{1} + D_{2} = 12 + 0 = 12$.
• The minimum is applied to $A_{2} = \min(A_{2}, L_{2}) = \min(5, 8) = 5$, the value of $B_{2} = 12$ remains the same.
• $A_{3} = A_{2} + D_{3} = 12$, $B_{3} = B_{2} + D_{3} = 19$.
• The minimum is applied to $A_{3} = \min(A_{3}, L_{3}) = 3$, the value of $B_{3} = 19$ remains the same.
• $A_{4} = A_{4} + D_{3} = 3$, $B_{4} = B_{3} + D_{4} = 19$.
• The minimum is applied to $A_{4} = \min(A_{4}, L_{4}) = 3$, the value of $B_{4} = 19$ remains the same.
• $A_{5} = A_{5} + D_{4} = 11$, $B_{5} = B_{4} + D_{5} = 27$.
• The value of $A_{5} = 11$ remains the same, $B_{5} = \min(B_{5}, R_{5}) = \min(27, 23) = 23$.
• $A_{5} + B_{5} = 11 + 23 = 34$.

It can be shown that this is the maximum value.

Scoring

The tests for this problem consist of six groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Please note that passing the example tests is not required for some groups. $\textbf{Offline-evaluation}$ means that the results of testing your solution on this group will only be available after the end of the competition.

Group	Points	Additional constraints	<	Required groups	Comment
		$n$	$D_i$
0		--	--	--	Examples.
1	13	$n \le 15$		0
2	18	$n \le 300$		0, 1
3	14	$n \le 5000$	$D_{i} = 0$	--
4	16		--	0--3
5	19	--	$D_{i} = 0$	3
6	20		--	0--5	Offline-evaluation.