Podziałem przedziału $[0, N)$ nazywamy ciąg liczb całkowitych $S = (s_0, \dots, s_r)$, który spełnia następujące trzy warunki:

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

Oznacza to, że dla każdego $i$, $[s_i, s_{i+1})$ reprezentuje przedział ciągły, a $[0, N)$ jest sumą tych $r$ przedziałów.

Dane są trzy ciągi o długości $N$ składające się z liczb całkowitych z zakresu od $-10^9$ do $10^9$: $A$ $(a_0, \dots, a_{N-1})$, $B$ $(b_0, \dots, b_{N-1})$ oraz $C$ $(c_0, \dots, c_{N-1})$.

Niech wynik (score) podziału $S$ będzie zdefiniowany jako $f(S)$ w następujący sposób:

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

Znajdź maksymalną wartość $f$ dla wszystkich możliwych podziałów $S$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $N$ ($1 \le N \le 2 \cdot 10^5$). Druga linia zawiera $N$ liczb całkowitych: $i$-ta z nich oznacza $a_i$. Trzecia i czwarta linia opisują odpowiednio ciągi $b$ oraz $c$ w tym samym formacie ($-10^9 \le a_i, b_i, c_i \le 10^9$).

Wyjście

Wypisz jedną liczbę całkowitą: maksymalny wynik spośród wszystkich możliwych podziałów.

Przykład

Wejście 1

2
1 -1
-1 4
1 -2

Wyjście 1

1

Wejście 2

1
1000000000
1000000000
1000000000

Wyjście 2

3000000000