23107번 - Efficient Partitioning 다국어

Let a partition of $[0, N)$ be an integer sequence $S = (s_0, \ldots, s_r$) that satisfies the following three conditions:

• $s_0 = 0$,
• $s_r = N$,
• $s_i < s_{i + 1}$ ($0 \le i < r$).

That is, for each $i$, $[s_i, s_i + 1)$ represents a continuous interval, and $[0, N)$ is the union of these $r$ intervals.

Given are three sequences of length $N$ consisting of integers between $-10^9$ and $10^9$: $A$ ($a_0, \ldots, a_{N-1}$), $B$ ($b_0, \ldots, b_{N-1}$), $C$ ($c_0, \ldots, c_{N-1}$).

Let the score of partition $S$ be $f(S)$ defined as follows:

$$ f(S)=\min_{0 \leq i < r}\left\{b_{s_i}+c_{s_{i+1}-1}+\sum_{s_i \leq j < s_{i+1}} a_j\right\} $$

Find the maximum value of $f$ over all possible partitions $S$.

The first line of input contains one integer $N$ ($1 \le N \le 2 \cdot 10^5$). The second line contains $n$ integers: $i$-th of them denotes $a_i$. The third and fourth lines describe the sequences $b$ and $c$ in the same format ($-10^9 \le a_i, b_i, c_i \le 10^9$).

Print one integer: the maximum score over all possible partitions.