시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB193327.273%

문제

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.

예제 입력 1

2
1 -1
-1 4
1 -2

예제 출력 1

1

예제 입력 2

1
1000000000
1000000000
1000000000

예제 출력 2

3000000000