효율적인 분할

$[0, N)$의 분할을 다음 세 조건을 만족하는 정수 수열 $S = (s_0, \ldots, s_r)$로 정의한다.

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

즉, 각 $i$에 대해 $[s_i, s_i + 1)$은 연속한 구간을 나타내고, $[0, N)$은 이 $r$개 구간의 합집합이다.

$-10^9$ 이상 $10^9$ 이하의 정수로 이루어진 길이 $N$의 수열 세 개가 주어진다. $A$ ($a_0, \ldots, a_{N-1}$), $B$ ($b_0, \ldots, b_{N-1}$), $C$ ($c_0, \ldots, c_{N-1}$)이다.

분할 $S$의 점수 $f(S)$를 다음과 같이 정의한다.

$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\}$

가능한 모든 분할 $S$에 대한 $f$의 최댓값을 구한다.

첫째 줄에 정수 $N$이 주어진다 ($1 \le N \le 2 \cdot 10^5$). 둘째 줄에 $N$개의 정수가 주어지며, $i$번째 정수가 $a_i$이다. 셋째 줄과 넷째 줄에도 같은 형식으로 수열 $b$와 $c$가 주어진다 ($-10^9 \le a_i, b_i, c_i \le 10^9$).

가능한 모든 분할 중 점수의 최댓값을 정수 하나로 출력한다.