Problem Description

You are given a sequence \( A = (a_0, ..., a_{N-1}), B = (b_0, ..., b_{N-1}), C = (c_0, ..., c_{N-1}) \) of length \( N \) consisting of integers between \( -10^9 \) and \( 10^9 \).

Consider dividing the sequence \( A \) into several contiguous subsequences. A division is represented by an integer sequence \( D = (d_0, ..., d_r) \) that satisfies the following conditions:

• \( d_0 = 0 \)
• \( d_r = N \)
• \( d_i < d_{i+1} \) for \( 0 \leq i < r \)

That is, for each \( i \), \( [d_i, d_{i+1}) \) represents a contiguous interval, and the entire sequence is the union of these \( r \) intervals.

Define a function \( f \) that returns the score for a division \( D \) as follows:

\[ f(D) = \min_{0 \leq i < r} \left\{ b_{d_i} + c_{d_{i+1}-1} + \sum_{d_i \leq j < d_{i+1}} a_j \right\} \]

Find the maximum value of \( f \) when the division is chosen optimally.

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_0 \) \( a_1 \) \( \cdots \) \( a_{N-1} \) \( b_0 \) \( b_1 \) \( \cdots \) \( b_{N-1} \) \( c_0 \) \( c_1 \) \( \cdots \) \( c_{N-1} \)

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

2
1 -1
-1 4
1 -2

Sample Output #1

1

Sample Input #2

1
1000000000
1000000000
1000000000

Sample Output #2

3000000000

Sample Input #3

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -728713779 573207953 115652694 -686953578 -215986240

Sample Output #3

91174984

Notes/Hints

Constraints

• All inputs are integers.
• \( 1 \leq N \leq 2 \times 10^5 \)
• \( -10^9 \leq a_i, b_i, c_i \leq 10^9 \) for \( 0 \leq i < N \)

Sample Explanation 1

For \( D = (0, 2) \), the score is \( b_0 + c_1 + a_0 + a_1 = -3 \). For \( D = (0, 1, 2) \), the score is \( \min(b_0 + c_0 + a_0, b_1 + c_1 + a_1) = \min(1, 1) = 1 \).

Sample Explanation 2

Be careful of overflow.

见题面 Input 部分

见题面 Output 部分