Vasile descarca de pe Internet
o aplicatie foarte interesanta. Aplicatia a fost împartita în mai
multe pachete, iar pachetele trebuie sa fie descarcate într-o ordine fixata.
Se cunoaste timpul de descarcare pentru fiecare pachet, precum si timpul necesar
instalarii fiecarui pachet (ambii timpi fiind exprimati în secunde).
Fiind nerabdator, Vasile vrea sa testeze aplicatia cât mai repede si deci
vrea sa înceapa instalarea chiar înainte de a se fi terminat descarcarea
tuturor pachetelor.
Dar stie ca o data ce a început instalarea aplicatiei, aceasta nu mai
poate fi întrerupta (va da eroare daca la momentul în care este
necesara instalarea unui pachet, acesta nu este complet descarcat).
Cerinta
Scrieti un program care sa determine numarul minim de secunde
(din momentul în care a început descarcarea) dupa care Vasile începe
instalarea aplicatiei.
Date de intrare
Pe prima linie a fisierului
de intrare pachete.in se afla
un numar natural N reprezentând
numarul de pachete.
Pe urmatoarele N linii se afla
informatiile despre pachete, în ordinea în care acestea trebuie
sa fie descarcate. Pe linia k+1
se afla doua numere naturale I D
separate printr-un spatiu cu semnificatia "timpul de instalare a pachetului
k este I,
iar timpul de descarcare a pachetului k
este D".
Date de iesire
Fisierul de iesire
pachete.out va contine o singura
linie pe care va fi scris numarul minim de secunde (din momentul în care
a început descarcarea) dupa care Vasile începe instalarea aplicatiei.
Restrictii
1 <= N <= 100 000
1 <= I, D <= 1000
Exemple
pachete.in
pachete.out
pachete.in
pachete.out
pachete.in
pachete.out
2 1
1 5
3 3
2 4
7
5
1 1
1 2
3 1
2 1
3 3
2
7
2 1
2 4
1 2
2 1
3 2
3 1
1 3
3
prof. Emanuela
Cerchez
Liceul de Informatica "Grigore Moisil" Iasi