$[0, N)$에 대한 분할(partition)을 다음 세 가지 조건을 만족하는 정수 수열 $S = (s_0, \dots, 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, \dots, a_{N-1})$, $B (b_0, \dots, b_{N-1})$, $C (c_0, \dots, c_{N-1})$이 주어진다.

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

$$f(S) = \min_{0 \le i < r} \left\{ b_{s_i} + c_{s_{i+1}-1} + \sum_{s_i \le 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$).

출력

가능한 모든 분할에 대한 점수의 최댓값을 정수로 출력하시오.

예제

입력 1

2
1 -1
-1 4
1 -2

출력 1

1

입력 2

1
1000000000
1000000000
1000000000

출력 2

3000000000