Problema lunii: faliment

O bancă a dat faliment; celelalte bănci doresc să preia clienții, dar nu chiar pe toți: pe cei mai profitabili.

Din fericire, o conjunctură favorabilă ne permitem să alegem primii (suntem reprezentații unei bănci de renume). Din nefericire, autoritățile de reglementare impun anumite condiții.

Clienții băncii falimentare sunt identificați prin numere cuprinse între 1 și N (sunt N clienți). Pentru fiecare client se cunoaște valoarea activelor sale (averea) și valoarea pasivelor sale (datoriile). Valoarea unui client este dată de diferența dintre active și pasive.

Condiția principală impusă de autorități este aceea că trebuie ales un interval de clienți; mai exact, putem alege două numere P și Q și atunci vom prelua toți clienții care sunt identificați prin numere cuprinse între P și Q. Va trebui să alegem cel puțin un client, dar dorim ca valoarea totală a clienților aleși să fie cât mai mare.

Datele de intrare se citesc de la intrarea standard. Pe prima linie se va afla numărul N al clienților. Fiecare dintre următoarele N linii conțin câte două numere separate printr-un spațiu; primul reprezintă valoarea activelor clientului corespunzător liniile respective, iar al doilea valoarea pasivelor. Există cel puțin un client și cel mult 1.000.000. Valorile activelor și pasivelor sunt numere cuprinse între 0 și 1.000.000.000.

Datele de ieșire se scriu la ieșirea standard. Va fi scris un singur număr reprezentând valoarea maximă a clienților aleși.

Exemplu

Intrare

Ieșire