设 $[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$ 个区间的并集。

给定三个长度为 $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\}$$

求 $f$ 在所有可能的划分 $S$ 下的最大值。

输入格式

第一行包含一个整数 $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