Three_Arrays (OOI final)
Time limit: 1 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: data structures, sorting, optimization, dynamic programming

# Three Arrays

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1 second        |
| Memory limit: | 512 megabytes   |

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

1.  A0 = a0, B0 = b0
2.  For all i from 1 to n, perform the following actions:

    a. Set the elements as Ai = A_{i-1} + Di and Bi = B_{i-1} + Di .
    b. Choose exactly one of the following operations and apply it:
        * Ai = min(Ai , Li)
        * Bi = min(Bi , Ri)

You want to construct arrays A and B to maximize the value of An + Bn. Find the maximum value of An + Bn that can be obtained by performing the described actions.

#### Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of arrays D, L, and R.

The second line contains n integers D1, D2, . . . , Dn (0 ≤ Di ≤ 10^9 ) — the array D.

The third line contains n integers L1, L2, . . . , Ln (0 ≤ Li ≤ 10^9 ) — the array L.

The fourth line contains n integers R1, R2, . . . , Rn (0 ≤ Ri ≤ 10^9 ) — the array R.

The fifth line contains two integers a0 and b0 (0 ≤ a0, b0 ≤ 10^9 ).

#### Output

Output a single integer — the maximum possible value of An + Bn among all possible ways to construct arrays A and B.

#### 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. 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 | n | Di | Required groups | Comment             |
|-------|--------|---|---|-----------------|---------------------|
| 0     | 0      | – | – | –               | Examples.           |
| 1     | 13     | n ≤ 15 | – | 0               |                     |
| 2     | 18     | n ≤ 300 | – | 0, 1            |                     |
| 3     | 14     | n ≤ 5000 | Di = 0 | –               |                     |
| 4     | 16     | n ≤ 5000 | – | 0–3             |                     |
| 5     | 19     | – | Di = 0 | 3               |                     |
| 6     | 20     | – | – | 0–5             | Offline-evaluation. |

## Example

| standard input | standard output |
|----------------|-----------------|
| 5              | 34              |
| 4 0 7 0 8      |                 |
| 10 5 3 7 7     |                 |
| 8 5 9 2 23     |                 |
| 4 8            |                 |

### Note

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

1. A0 = 4, B0 = 8.
2. A1 = A0 + D1 = 4 + 4 = 8, B1 = B0 + D1 = 8 + 4 = 12.
3. The minimum is applied to A1 = min(A1, L1) = min(10, 8) = 8, the value of B1 = 12 remains the same.
4. A2 = A1 + D2 = 8 + 0 = 8, B2 = B1 + D2 = 12 + 0 = 12.
5. The minimum is applied to A2 = min(A2, L2) = min(5, 8) = 5, the value of B2 = 12 remains the same.
6. A3 = A2 + D3 = 5 + 7 = 12, B3 = B2 + D3 = 12 + 7 = 19.
7. The minimum is applied to A3 = min(A3, L3) = min(12, 3) = 3, the value of B3 = 19 remains the same.
8. A4 = A3 + D4 = 3 + 0 = 3, B4 = B3 + D4 = 19 + 0 = 19.
9. The minimum is applied to A4 = min(A4, L4) = min(3, 3) = 3, the value of B4 = 19 remains the same.
10. A5 = A4 + D5 = 3 + 8 = 11, B5 = B4 + D5 = 19 + 8 = 27.
11. The value of A5 = 11 remains the same, B5 = min(B5, R5) = min(27, 23) = 23.
12. A5 + B5 = 11 + 23 = 34.

It can be shown that this is the maximum value.

Starter code:

Grader code:

Setup script:

Evaluation script: