Fişierul intrare/ieşire:	pudge.in, pudge.out	Sursă	FMI No Stress 9
Autor	Stelian Chichirim	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pudge

Pudge este pozitionat in punctul (X,Y) in plan si are un hook de latime D (D e par).
Acesta poate arunca hook-ul in orice punct (X₀, 0), 0 <= X₀ <= X intreg; timpul hook-ului sa ajunga pe axa Ox este egal cu lungimea segmentului format de pozitia lui Pudge si punctul in care arunca hook-ul.
Pe axa Ox sunt mai multi inamici, fiecare inamic este la o pozitie P_i si are o viteza constanta V_i pe unitate de timp (toti inamicii se misca pe axa Ox spre +infinit).
Daca pudge arunca hook-ul in punctul X₀, acesta va prinde toti inamicii care sunt in intervalul [X₀-D/2, X₀+D/2] in momentul de timp in care hook-ul ajunge pe axa Ox.
Calculati numarul maxim de inamici pe care ii poate prinde pudge dintr-o aruncare a hook-ului.

Date de intrare

Fişierul de intrare pudge.in contine pe prima linie X, Y, D si N, care semnifica numarul de inamici.
Urmeaza N linii, fiecare avand 2 numere P_i, pozitia initiala a inamicului, si V_i, viteaza acestuia.

Date de ieşire

În fişierul de ieşire pudge.out se va afisa numarul maxim de inamici pe care ii poate prinde pudge.

Restricţii

• 1 <= N <= 100.000
• 0 <= X, Y, D <= 10⁸, numere intregi
• 0 <= P_i <= 10⁸ intreg, 0 <= V_i <= 10 intreg, pentru fiecare inamic.
• 0 <= X₀ <= X
• Pudge arunca hook-ul la momentul 0.
• Pentru 20% din punctaj V_i = 0 pentru toti inamicii si 0 <= X, Y, D, P_i <= 10⁶.
• Pentru alte 20% din punctaj 1 <= N <= 1000 si 0 <= X, Y, D, P_i <= 1000.
• Pentru alte 40% din punctaj 0 <= X, Y, D, P_i <= 10⁶.
• Pentru alte 20% din punctaj restrictiile initiale.

Exemplu

Explicaţie

Pentru primul exemplu:

Pudge poate arunca hook-ul in punctul 8 pentru a prinde 3 inamici. Hook-ul va ajunge pe axa Ox in punctul 8 la timpul .

Cum se trimit solutii?