Rezolvare PBinfo #4675

Fermierul Petrică are o livadă cu n pomi fructiferi, pentru fiecare cunoscându-se coordonatele, în sistemul cartezian de coordonate xOy. Da, Petrică are și vădite calități de matematician!

Pentru a culege fructe, Petrică închiriază o mașină foarte performantă (și scumpă) cu care trece prin livadă o singură dată pe o direcție paralelă cu axa Oy. Mașina are o lățime cunoscută L și culege fructele din toți pomii pe care îi întâlnește.

Cerința

Determinați numărul maxim de pomi din care pot fi culese fructele la o trecere a mașinii prin livadă.

Date de intrare

Fișierul de intrare livada.in conține pe prima linie pe prima linie numerele n L. Pe următoarele n linii se află câte o pereche de numere x y, reprezentând coordonatele pomilor din livada lui Petrică.

Date de ieșire

Fișierul de ieșire livada.out va conține un număr natural M, reprezentând numărul maxim de pomi din care pot fi culese fructele la o trecere a mașinii prin livadă.

Restricții și precizări

• n ≤ 100 000;
• -109 ≤ x,y ≤ 109;
• 1 ≤ L ≤ 2*109;
• în mod surprinzător, este posibil ca mai mulți pomi să aibă aceleași coordonate;
• pentru teste în valoare de 40 de puncte, 1 ≤ x,y,L ≤ 1000;

Exemplu:

livada.in

8 3
1 1
6 2
4 1
-1 4
-3 1
1 3
-5 -1
2 -1

livada.out

4

Explicație