O colonie de furnici a construit un tunel lung, în linie dreaptă. Fiecare familie de furnici din colonie şi-a stabilit de-a lungul tunelului o aşezare, în care locuiesc toate furnicile din familie şi unde îşi păstrează şi proviziile pentru iarnă.
Furnicuţele sunt foarte harnice şi au adunat cantităţi de provizii impresionante, care depăşesc nevoile lor. Prin urmare, regina furnică a decis – pentru a spulbera prejudecăţile şi pentru a înveseli colonia – ca fiecare familie de furnici să invite în ziua de Crăciun câţiva greieri (acelaşi număr de greieri pentru fiecare familie).
Se cunoaşte numărul de boabe de grâu adunate în plus (care pot fi oferite greierilor) de fiecare familie de furnici şi faptul că fiecare greiere va fi servit cu exact o boabă de grâu.
Boabele de grâu adunate de o familie pot fi consumate în familia respectivă, sau pot fi donate altor familii, caz în care grâul trebuie transportat. Dar furnicile care asigură transportul, consumă o boabă de grâu pentru fiecare metru de drum prin tunel (indiferent de cantitatea transportată).
Cerinţă
Scrieţi un program care să determine numărul maxim de greieri care pot fi găzduiţi în fiecare familie de furnici (acelaşi pentru toate familiile).
Date de intrare
Fişierul de intrare ants.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 de furnici. Mai exact, pe linia i+1 se află două numere naturale separate prin spaţiu Ai Bi, unde Ai reprezintă poziţia în care locuieşte familia de furnici i (exprimată în număr de metri faţă de intrarea în tunel), iar Bi reprezintă numărul de boabe de grâu adunate în plus de familia i. Familiile sunt specificate în ordinea în care se află plasate în tunel.
Date de ieşire
Fişierul de ieşire ants.out va conţine o singură linie pe care va fi scris numărul maxim de greieri ce pot fi găzduiţi de fiecare familie de furnici.
Restricţii
1 ≤ N ≤ 100 000
1 ≤ Ai ≤ 1 000 000 000, 0 ≤ Bi ≤ 1 000 000 000, pentru orice i=1, 2, …, N
Nu există două familii situate în aceeaşi poziţie.
Exemple
ants.in
ants.out
Explicaţii
4
20 300
40 400
340 700
360 600
415
Există 4 familii de furnici, situate la 20 m de intrarea în tunel, 40 m, 340 m şi respectiv 360 m.
Fiecare familie va găzdui 415 greieri.
Familia 1 are 300 de boabe de grâu surplus şi mai poate primi 115 boabe de la familia 2. Aceste boabe trebuie să fie transportate pe o distanţă de 20 m, deci familia 2 va rămâne cu 400-115-20=265 boabe de grâu.
Familia 2 are acum 265 de boabe de grâu şi mai poate primi 150 boabe de grâu de la familia 3 (acestea vor fi transportate pe distanţa de 300 m). Deci familia 3 are acum 700-300-150=250 boabe de grâu. Prin urmare familia 3 va primi de la familia 4, 165 boabe de grâu care vor fi transportate pe o distanţă de 20m. Deci familia 4 rămâne cu 600-20-165=415 boabe.
Fiecare familie poate găzdui 415 greieri şi acesta este cel mai mare număr de greieri posibil.