Soit une partition de $[0, N)$ une suite d'entiers $S = (s_0, \dots, s_r)$ qui satisfait les trois conditions suivantes :

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

C'est-à-dire que pour chaque $i$, $[s_i, s_{i+1})$ représente un intervalle continu, et $[0, N)$ est l'union de ces $r$ intervalles.

On donne trois suites de longueur $N$ composées d'entiers compris entre $-10^9$ et $10^9$ : $A$ $(a_0, \dots, a_{N-1})$, $B$ $(b_0, \dots, b_{N-1})$, $C$ $(c_0, \dots, c_{N-1})$.

Soit le score de la partition $S$ défini par $f(S)$ comme suit :

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

Trouvez la valeur maximale de $f$ parmi toutes les partitions $S$ possibles.

Entrée

La première ligne de l'entrée contient un entier $N$ ($1 \le N \le 2 \cdot 10^5$). La deuxième ligne contient $N$ entiers : le $i$-ième d'entre eux désigne $a_i$. Les troisième et quatrième lignes décrivent les suites $b$ et $c$ dans le même format ($-10^9 \le a_i, b_i, c_i \le 10^9$).

Sortie

Affichez un entier : le score maximal parmi toutes les partitions possibles.

Exemples

Entrée 1

2
1 -1
-1 4
1 -2

Sortie 1

1

Entrée 2

1
1000000000
1000000000
1000000000

Sortie 2

3000000000