Sea una partición de $[0, N)$ una secuencia de enteros $S = (s_0, \dots, s_r)$ que satisface las siguientes tres condiciones:

• $s_0 = 0$,
• $s_r = N$,
• $s_i < s_{i+1}$ ($0 \le i < r$).

Es decir, para cada $i$, $[s_i, s_{i+1})$ representa un intervalo continuo, y $[0, N)$ es la unión de estos $r$ intervalos.

Se dan tres secuencias de longitud $N$ que consisten en enteros entre $-10^9$ y $10^9$: $A$ $(a_0, \dots, a_{N-1})$, $B$ $(b_0, \dots, b_{N-1})$, $C$ $(c_0, \dots, c_{N-1})$.

Sea la puntuación de la partición $S$, $f(S)$, definida de la siguiente manera:

$$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\}$$

Encuentre el valor máximo de $f$ sobre todas las particiones posibles $S$.

Entrada

La primera línea de la entrada contiene un entero $N$ ($1 \le N \le 2 \cdot 10^5$). La segunda línea contiene $N$ enteros: el $i$-ésimo de ellos denota $a_i$. La tercera y cuarta líneas describen las secuencias $b$ y $c$ en el mismo formato ($-10^9 \le a_i, b_i, c_i \le 10^9$).

Salida

Imprima un entero: la puntuación máxima sobre todas las particiones posibles.

Ejemplos

Entrada 1

2
1 -1
-1 4
1 -2

Salida 1

1

Entrada 2

1
1000000000
1000000000
1000000000

Salida 2

3000000000