Marele vrăjitor Prospero are o grădină minunată îngrijită de o sumedenie de spiriduşi care n-au altă sarcină decât să zboare la orele dimineţii de-a lungul aleilor şi să stropească plantele din vasele ornamentale de piatră aflate pe margine. Există un havuz chiar la capătul grădinii şi o alee principală ce porneşte de la havuz şi duce până la intrare. Din aleea principală se desprind alei secundare ce formează ronduri alungite revenind, în acelaşi loc, la aleea principală.
Se ştie că există n spiriduşi, numerotaţi de la 1 la n, fiecare pentru câte una dintre aleile secundare. Toţi pornesc de la havuz la ora 5:00:00 dimineaţa cu câte un vas cu apă pregătit de cu seară, străbat aleea principală până la rondul lor, apoi parcurg aleea rondului propriu, revin în aleea principală, se întorc la havuz pentru a se alimenta cu apă şi o iau de la capăt la fel, până la ora 9:00:00 când se retrag la umbră pentru somn. Se ştie că toţi spiriduşii zboară fără încetare, cu aceeaşi viteză, pe toată durata celor exact 4 ore. Se cunosc, pentru fiecare spiriduş, numărul de secunde necesare pentru a ajunge de la havuz la rondul propriu şi numărul de secunde necesare pentru a parcurge în întregime rondul propriu. Orice spiriduş care ajunge la havuz îşi umple vasul în exact o secundă, de la un robinet aflat pe marginea havuzului. De exemplu, dacă spiriduşul care se ocupă de rondul 5 din figură are nevoie de 2 secunde pentru a ajunge la rondul său şi de 15 secunde pentru a parcurge rondul 5, atunci va reveni la havuz pentru a-şi umple vasul la orele 5:00:19 (2+15+2), îşi umple vasul şi porneşte iar la ora 5:00:20, revine iar la 5:00:39 şi pleacă iar la ora 5:00:40 etc.
Doi spiriduşi nu îşi pot umple vasul în acelaşi moment de la acelaşi robinet.
Cerinţă
Se cere să se determine numărul minim de robinete cu care trebuie să fie prevăzut havuzul astfel încât nici un spiriduş, în nici un moment, să nu fie nevoit să aştepte pentru a-şi putea umple vasul cu apă.
Date de intrare
Din fişierul elfi.in se citesc:
- n numărul de spiriduşi, de pe primul rând
- n perechi de forma ci pi reprezentând numărul de secunde de la havuz la rondul propriu şi respectiv numărul de secunde necesar pentru parcurgerea rondului propriu, de pe următoarele n linii ale fişierului.
Date de ieşire
În fişierul elfi.out se scrie o singura linie cu un singur număr reprezentând numărul minim de robinete necesare.
Restricţii
1<n<5001
0<ci<101
0<pi<101
Exemple
elfi.in
elfi.out
Explicaţii
5
7 4
7 8
4 5
7 6
2 15
4
Primul, al treilea, al patrulea şi al cincilea spiriduş se întâlnesc simultan la havuz la ora 7 :12 :59 şi-şi umplu vasele până la ora 7 :13 :00
