$[0, N)$ の分割とは、以下の3つの条件を満たす整数列 $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$ 個の区間の和集合となる。

長さ $N$ の整数列 $A = (a_0, \dots, a_{N-1})$、$B = (b_0, \dots, b_{N-1})$、$C = (c_0, \dots, c_{N-1})$ が与えられる。各要素は $-10^9$ から $10^9$ の範囲である。 分割 $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$ の最大値を求めよ。

入力

入力の1行目には整数 $N$ ($1 \le N \le 2 \cdot 10^5$) が与えられる。 2行目には $N$ 個の整数が与えられ、$i$ 番目の値は $a_i$ を表す。 3行目と4行目には、同様の形式で数列 $B$ と $C$ が与えられる ($-10^9 \le a_i, b_i, c_i \le 10^9$)。

出力

可能なすべての分割におけるスコアの最大値を1つの整数で出力せよ。

入出力例

入力 1

2
1 -1
-1 4
1 -2

出力 1

1

入力 2

1
1000000000
1000000000
1000000000

出力 2

3000000000