elfi

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 de intrare elfi.in se citesc:

• $n$, numărul de spiriduși, de pe primul rând;
• $n$ perechi de forma $c_i \ p_i$ 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 de ieșire elfi.out se scrie o singura linie cu un singur număr reprezentând numărul minim de robinete necesare.

Restricții și precizări

• $2 \leq n \leq 5 \ 000$;
• $1 \leq c_i \leq 100$;
• $1 \leq p_i \leq 100$;

Exemplu

elfi.in

5
7 4
7 8
4 5
7 6
2 15

elfi.out

4

Explicație

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$.