Missioni segrete

Il Commissario Basettoni ha presentato a Topolino le missioni che egli dovrà svolgere segretamente nel corso dell’anno.

Per ogni missione, oltre al luogo da raggiungere, Basettoni ne indica la durata in giorni e la data massima entro cui deve essere completata.
In altri termini, la missione può iniziare in qualunque giorno dell’anno ma deve durare esattamente il numero di giorni indicato e terminare non oltre la data di scadenza.

Topolino, presa la lista delle missioni ricevuta da Basettoni, ordina tali missioni in base alla loro data di scadenza.
Quindi, numera i giorni dell’anno da 1 a 365 (non esistono anni bisestili a Topolinia) e trasforma le date di scadenza in numeri secondo tale numerazione.

Per esempio, se una missione dura 15 giorni e deve essere svolta entro il 18 febbraio, Topolino la vede semplicemente come una coppia di interi 15 49 (in quanto il 18 febbraio è il quarantanovesimo giorno dell’anno).

Poiché può effettuare una sola missione alla volta, Topolino non sarà in grado di svolgerle tutte, pur iniziando una missione il giorno immediatamente successivo a quello in cui termina la precedente.
Vuole perciò sapere il numero massimo di missioni che è in grado di eseguire rispettando i vincoli sulla loro durata e scadenza.
Supponendo che Topolino già fornisca le coppie di interi ordinate per scadenza (il secondo membro delle coppie), aiutatelo a calcolare il massimo numero di missioni che può svolgere.

Per esempio, se ci sono quattro missioni, una di tre giorni da terminare entro il 5 gennaio, una di quattro giorni entro l’8 gennaio, una di tre giorni entro il 9 gennaio e una di 6 giorni entro il 12 gennaio, Topolino vi fornisce la lista di quattro coppie 3 5, 4 8, 3 9 e 6 12.
Il numero massimo di missioni che può svolgere è pari a tre, ossia le missioni corrispondenti alle coppie 3 5, 3 9 e 6 12:

• la prima missione inizia il primo di gennaio e termina il 3 gennaio;
• la seconda inizia il 4 gennaio e termina il 6 gennaio;
• la terza inizia il 7 gennaio e termina il 12 gennaio.

Notare che, scegliendo la missione corrispondente alla coppia 4 8, Topolino può svolgere al più due missioni.

Dati di input

Il file input.txt è composto da N+1 righe.

• La prima riga contiene un intero positivo che rappresenta il numero N di missioni presentate da Basettoni a Topolino.
• Le successive N righe rappresentano durata e scadenza delle missioni: ciascuna riga è composta da due interi d e s separati da uno spazio, a rappresentare che la corrispondente missione dura d giorni e deve essere completata entro l’s-esimo giorno dell’anno.

 

Dati di output

Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo numero di missioni che Topolino può svolgere rispettando i vincoli su durata e scadenza.

Assunzioni

• 1 ≤ N ≤ 100
• 1 ≤ d, s ≤ 365
• d ≤ s.

 

Esempio