Пусть разбиение (partition) отрезка $[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\}$$

Найдите максимальное значение $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