criza

Criza

== include(page="template/taskheader" task_id="criza") ==

Poveste şi cerinţă...

Primăria localitaţii CCEX a construit o şosea in linie dreaptă. Fiecare familie din oraş şi-a stabilit de-a lungul şoselei o aşezare în care locuiesc toţi membrii familiei şi unde îşi păstrează şi proviziile. Cetăţenii oraşului sunt foarte harnici şi au adunat cantităţi de provizii impresionante, care depăşesc nevoile lor. Prin urmare, primarul a decis ca fiecare familie să invite în ziua de 6 iunie câţiva prieteni (acelaşi număr de prieteni pentru fiecare familie).
Se cunoaşte numărul de porţii adunate în plus (care pot fi oferite prietenilor) de fiecare familie şi faptul că fiecare prieten va fi servit cu exact o porţie.
Proviziile adunate de o familie pot fi consumate în familia respectivă, sau pot fi donate altor familii, caz în care proviziile trebuie transportate. Familiile care asigură transportul consumă o porţie pentru fiecare metru de drum pe şosea, indiferent de cantitatea transportată.
Scrieţi un program care să determine numărul maxim de prieteni care pot fi găzduiţi în fiecare familie (acelaşi pentru toate familiile).

h2. Date de intrare

Fişierul de intrare $criza.in$ ...

Fişierul de intrare $criza.in$ conţine pe prima linie un număr natural $N$ care reprezintă numărul de familii. Următoarele $N$ linii conţin informaţii despre familiile din oraş. Mai exact, pe linia $i+1$ se află două numere naturale separate prin spaţiu $A{~i~} B{~i~}$, unde $A{~i~}$ reprezintă poziţia în care locuieşte familia $i$ (exprimată în număr de metri faţă de intrarea pe şosea), iar {$B{~i~}$} reprezintă numărul de porţii adunate în plus de familia $i$. Familiile sunt specificate în ordinea în care se află plasate pe şosea.

h2. Date de ieşire

În fişierul de ieşire $criza.out$ ...

Fişierul de ieşire $criza.out$ va conţine o singură linie pe care va fi scris numărul maxim de prieteni ce pot fi găzduiţi de fiecare familie.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ A{~i~} ≤ 10^9^, 0 ≤ B{~i~} ≤ 10^9^$
* Nu există două familii situate în aceeaşi poziţie

h2. Exemplu
table(example). |_. criza.in |_. criza.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

|4
20 300
40 400
340 700
360 600
|415|

== include(page="template/taskfooter" task_id="criza") ==

3974