Ion este cel mai apreciat maseur din oras. In fiecare zi, inainte de a se duce
la serviciu, Ion se conecteaza la Internet si citeste mail-ul in care secretara
firmei anunta programarile existente pentru ziua respectiva. Pentru fiecare
persoana programata, este precizat momentul in care va sosi si durata tratamentului
solicitat.
Tura lui Ion dureaza N
minute. Cand Ion ajunge la serviciu, incepe sa efectueze tratamentele programate.
Daca Ion este ocupat atunci cand soseste o persoana programata, persoana va
fi preluata de catre colegii lui Ion. Cand termina un tratament, el poate sa
bea o cafea, poate citi ziarul etc, pana cand soseste urmatoarea persoana.
Daca exista mai multe persoane care sosesc in acelasi moment, el poate sa aleaga
pe oricare dintre ele (restul le va "pasa" colegilor sai). În
functie de alegerile facute, Ion poate petrece mai mult timp la cafea sau dimpotriva.
Cerinta
Scrieti un program care sa determine numarul maxim de minute pe care Ion le
poate petrece la cafea.
Date de intrare
Prima linie a fisierului de intrare cafea.in
contine doua numere naturale N
si K, separate prin spatiu,
reprezentand durata turei lui Ion, exprimata in minute, respectiv numarul de
persoane programate in ziua respectiva.
Fiecare dintre urmatoarele K
linii contine informatii despre o persoana programata. Mai exact, pentru o persoana
sunt specificate doua numere naturale P
si T, separate prin spatiu.
Numarul P indica in al
catelea minut de la inceputul turei lui Ion soseste persoana respectiva, iar
T durata tratamentului,
exprimata in minute.
Date de iesire
Fisierul de iesire cafea.out
contine o singura linie pe care este afisat numarul maxim de minute pe care
Ion le poate petrece la cafea.
Restrictii
N <= 10000
1 <= K <= 10000
1 <= P <= N
1 <= P+T-1 <=
N
Exemple
cafea.in
cafea.out
15 6
1 2
1 6
4 11
8 5
8 1
11 5
4
cafea.in
cafea.out
10 6
2 4
2 2
2 1
4 7
8 3
8 1
5
cafea.in
cafea.out
10 3
1 2
4 3
5 1
5
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi