pudge

Pudge

== include(page="template/taskheader" task_id="pudge") ==

Pudge este pozitionat in punctul (X,Y) in plan si are un hook de latime D+1 (D e par).
Acesta poate arunca hook-ul in orice punct intreg X{~0~}, 0 <= X{~0~} <= X; 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 spre +infinit).
Daca pudge arunca hook-ul in punctul X{~0~}, acesta va prinde toti inamicii care sunt in intervalul [X{~0~}-D/2,X{~0~}+D/2] in momentul de timp in care hook-ul ajunge pe axa Ox.

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), 0 <= X{~0~} <= 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{~0~}, acesta va prinde toti inamicii care sunt in intervalul [X{~0~}-D/2, X{~0~}+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.
h2. Date de intrare

h2. Restricţii

* 1 <= N <= 100.000
* 0 <= X, Y, D <= 10^8^
* 0 <= P{~i~} <= 10^8^, 0 <= V{~i~} <= 10, pentru fiecare inamic.
* {* 0 <= X{~0~} <= X *}
* Pentru 20% din punctaj V{~i~} = 0 pentru toti inamicii si 0 <= X, Y, D, P{~i~} <= 10^6^.
* 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^6^.
* Pentru alte 20% din punctaj restrictiile initiale.

* $1$ <= N <= $100.000$
* $0$ <= X, Y, D <= $10^8^$, numere intregi
* $0$ <= P{~i~} <= $10^8^$ intreg, $0$ <= V{~i~} <= $10$ intreg, pentru fiecare inamic.
* 0 <= $X{~0~}$ <= 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^6^$.
* 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^6^$.
* Pentru alte $20%$ din punctaj restrictiile initiale.

h2. Exemplu
table(example). |_. pudge.in |_. pudge.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10 2 4 5
12 1
2 2
7 0
4 1
3 4
| 3 |
| 100 5 20 6
15 1
50 0
20 2
70 1
50 5
30 2
| 2

|
h3. 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 <tex> \sqrt{8} </tex>.

== include(page="template/taskfooter" task_id="pudge") ==