Este primul an în care se organizează concursul ForCoding. Știind că dacă concursul va avea succes, acesta va putea trece de granițele județului, toți elevii din oraș s­-au înscris imediat.

Concursul s­-a desfășurat conform programului,iar elevii au fost încântați. S-­au obținut atât punctaje mari, cât și punctaje mai mici, dar toți au avut de câștigat experiență. Acum, treaba comisiei este să realizeze niște statistici asupra rezultatelor.

Se știe că la concurs au participat N elevi, fiecare având punctaj un număr natural. Comisia dorește să găsească un subșir de sumă maximă, punând următoarea condiție: pentru fiecare elev există o limită atât la stânga left [] cât și la dreapta right[] în care nu se mai poate alege un alt elev. Cu alte cuvinte, dacă am selectat punctajul elevului i pentru subșir, nu mai putem selecta un elev din intervalul [ i­-left[i],i+right[i] ]. De ce? Din motive de siguranță, împotriva fraudei.

Cerința

Ajutați comisia să găsească subșirul de sumă maximă.

Date de intrare

Fișierul forcoding.in ​va ​conține pe prima linie numărul natural N reprezentând numărul de elevi participanți la concurs.
Pe a doua linie se află cele N punctaje, al i-­lea număr, reprezentând punctajul celui de-­al i-­lea elev. Indexarea elementelor începe de la poziția 1.

Pe a treia linie sa află elementele limitei left[], left[i] reprezentând limita la stânga pentru elevul i.

Pe a patra linie se află elementele limitei right[], right[i] reprezentând limita la dreapta pentru elevul i.

Date de ieșire

Fișierul de ieșire forcoding.out va conține pe prima linie numărul S, suma punctajelor elevilor, respectând cerința comisiei.

Restricții și precizări

• 1 <= N <= 10000

• i+right[i]<=N pentru orice i

• i­left[i]>=1 pentru orice i

• Punctajul fiecărui elev este un număr natural pozitiv <= 104

• Pentru 30% dintre teste N <= 16

Exemplu:

forcoding.in

8
9 11 2 8 5 9 54 21
0 0 2 2 3 1 4 5
1 0 4 2 3 1 1 0

forcoding.out

65

Explicație

Se alege elevul de pe poziția 7(cu punctajul 54).

Se observă că nu mai putem alege nimic la dreapta, iar la stânga putem alege abia de la elevul de pe poziția 7­-left[7]-­1= 2. Îl vom alege pe acesta (cu punctajul 11), iar acesta va fi subșirul de sumă maximă,având suma 54 + 11 = 65