Fișierul intrare/ieșire	competitie.in, competitie.out	Sursă	Shumen 2010, Juniori
Autor	autor necunoscut	Adăugată de	Stoica Vlad • vladstoick
Timp de execuție pe test	1 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Competitie

K concurenti participa la o intrecere. Fiecare dintre ei trebuie sa faca N tururi. Toti concurentii pleaca in acelasi timp de la linia de pornire. La inceput fiecare concurrent se simte normal, insa cand termina o tura el isi pierde din capacitatea de a conduce. Astfel fiecare cursa e cu o milisecunda mai inceata decat cea dinainte. La inceput concurentul i face un tur in ms_i milisecunde ( ms_i este un numar natural nenul ). Regulile spun ca fiecare concurent i are dreptul la fiecare p_i (1 ≤ p_i ≤ N) ture efectuate sa primeasca cand trece linia de sosire o bautura energizanta ce il readuce la forma normala. Fiecare concurent va trece linia de sosire de N ori(vom numara ultima trecere , insa nu si pe cea de la inceput )

Date de intrare

Pe prima linie din fisierul competitie.in se vor gasi doua numere : K si N. Pe urmatoarele K linii se gasesc doua numere ms_i si p_i.

Date de ieșire

Fisierul competitie.out va contine numarul maxim de concurenti ce trec linia de start in acelasi timp.

Restricții

• K ≤ 10 000
• N ≤ 1 000
• ms_i ≤ 1 000 000
• 1 ≤ p_i ≤ N

Exemplu

Explicație

Durata fiecarei curse pentru
Concurentul 1 – 26 , 27 , 26 ms
Concurentul 2 – 39 , 40 , 41 ms
Concurentul 3 – 45 , 45 , 45 ms
Concurentul 4 – 56 , 57 , 56 ms
Milisecunda in care trece linia de sosire pentru
Concurentul 1 – 26 , 53 , 79 ms
Concurentul 2 – 39 , 79 , 120 ms
Concurentul 3 – 45 , 90 , 135 ms
Concurentul 4 – 56 , 113 , 169 ms
In secunda 79 vor trece doi concurenti : cei cu numarul 1 si 2 .