令 $[0, N)$ 的一個分割為整數序列 $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$ 的序列，其元素為介於 $-10^9$ 與 $10^9$ 之間的整數：$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
1
1000000000
1000000000
1000000000

輸出 2

3000000000