La Banda Bassotti è stata rimessa in libertà. Zio Paperone, in partenza per un viaggio di K giorni, ha la necessità di far sorvegliare il deposito: quindi ha bisogno che sia sempre presente almeno una persona. Per risparmiare, decide di chiedere la disponibilità di amici e parenti, e ognuno di questi fornisce un intervallo di giorni in cui è disponibile per la sorveglianza. Paperone però sa che dovrà fare un regalo a ognuna delle persone che userà, e volendo risparmiare al massimo deve coinvolgere il minimo numero di persone, senza lasciare mai il deposito scoperto. In questo modo riuscirà a risparmiare sui regali.
Per esempio, supponiamo che il viaggio di Zio Paperone sia di K=8 giorni, con partenza il giorno 0 e ritorno il giorno K-1=7 e che le disponibilità siano le seguenti (per ogni nome, tra parentesi si indicano il giorno iniziale e il giorno finale della disponibilità).
In questo caso, a Zio Paperone basta coinvolgere Paperoga, Paperino e Archimede per assicurarsi che il deposito sia sempre sorvegliato, e se la cava con tre regali.
Sapendo il numero di giorni di viaggio, e le disponibilità di ognuno, il vostro compito è quello di aiutare Zio Paperone a calcolare il minimo numero di persone che servono ad assicurare una sorveglianza continua al deposito.
Il file di input è costituito da 2+N righe. La prima riga contiene un intero positivo K, ovvero il numero di giorni del viaggio. La seconda riga contiene un intero positivo N, il numero di persone che hanno dato la disponibilità a Zio Paperone. Le restanti N righe contengono una coppia di interi A e B per ognuna delle N persone: questa coppia di interi rappresenta l'inizio e la fine della disponibilità della i-esima persona.
Il file di output deve contenere un solo intero positivo R, che è il numero minimo di persone necessarie ad assicurare una sorveglianza continua al deposito.
| File input.txt | File output.txt |
8
5
3 5
0 2
1 3
5 6
4 7
| 3
|
| File input.txt | File output.txt |
10
6
2 5
0 2
1 3
5 6
4 7
7 9
| 4
|