P13507 [OOI 2024] Three Arrays

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$.

### 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 | 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 | $n \le 5000$ | -- | 0--3 | | | 5 | 19 | -- | $D_{i} = 0$ | 3 | | | 6 | 20 | -- | -- | 0--5 | **Offline-evaluation.** |