FMI NO STRESS 12 | Antisense

Cerință

Se dau două șiruri, $A$ și $B$, a câte $N$ numere fiecare, indexate de la $1$. Să se găsească valoarea maximă a expresiei $(A_{l}+A_{l+1}+...+A_{r}) - (B_{l}+B_{l+1}+...+B_{r})$, cu $1 \leq l \leq r \leq N$.

Date de intrare

Pe prima linie se găsește numărul natural $N$. Pe a doua linie se găsesc, în ordine, cele $N$ elemente ale șirului $A$. Pe a treia linie se găsesc, în ordine, cele $N$ elemente ale șirului $B$.

Date de ieșire

Se va afișa un singur număr, reprezentând valoarea maximă a expresiei de mai sus.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $-10^9 \leq A_{i}, B_{i} \leq 10^9, \forall i \in \{1, 2, \dots, N\}$;
• Pentru teste în valoare de $26$ de puncte, $1 \leq N \leq 100$;
• Pentru teste în valoare de alte $27$ de puncte, $1 \leq N \leq 2 \ 000$;
• Pentru restul de $47$ de puncte nu există restricții suplimentare.

Exemplu

stdin

5
7 6 10 6 -1
10 -1 22 0 -4

stdout

9

Explicație

Vom alege $l=4$ și $r=5$ și obținem $(6 + (−1)) − (0 + (−4)) = 5 - (-4) = 9$. Această valoare este maximă.