Fie două şiruri de lungime N de numere întregi a1, a2, ..., aN şi respectiv b1, b2, ..., bN.
Alegând anumiţi indici 1 <= i1 < i2 < … < ik <= N, formăm sumele Sa = ai1 + ai2 + … + aik şi Sb = bi1 + bi2 + ... + bik.
Cerinţă
Să se determine suma Sa maximă care se poate obţine alegând şirul de indici i1, i2, ..., ik astfel încât suma Sb să nu fie negativă.
Date de intrare
Fişierul de intrare siruri3.in conţine pe prima linie un număr natural N reprezentând lungimea şirurilor. Urmează N linii. Linia i+1 va conţine valorile ai şi bi separate printr-un spaţiu.
Date de ieşire
Fişierul de ieşire siruri3.out va conţine un singur număr natural reprezentând suma maximă Sa care se poate forma astfel încât suma Sb să nu fie negativă.
Restricţii
3 <= N <= 1000
Valorile memorate în siruri sunt numere întregi cuprinse între -100 şi 100
Se garantează că pentru datele de intrare se poate obţine o soluţie validă cu Sb >= 0
Exemple
siruri3.in
siruri3.out
Explicaţii
3
1 -5
-4 8
1 -1
-2
Şirul a este: 1 -4 1
Şirul b este: -5 8 -1
Suma maximă se obţine alegând toate numerele:
Sa = 1 + (-4) + 1 = -2
Sb = (-5) + 8 + (-1) = 3 >= 0
siruri3.in
siruri3.out
Explicaţii
5
-1 -3
7 -3
-1 8
5 -11
3 -1
9
Suma maximă se obţine alegând numerele de pe poziţiile 2, 3, 5:
Sa = 7 + (-1) + 3 = 9
Sb = -3 + 8 + (-1) = 4 >= 0
student Gabriel Mititelu şi student Andrei Bistriceanu