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 (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.

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 X0 pe axa Ox; timpul hook-ului sa ajunga pe axa Ox este egal cu distanta dreptei formata de pozitia lui Pudge si punctul in care arunca hook-ul.
Pe axa Ox sunt mai multi inamici, fiecare inamic este la o pozitie Pi si are o viteza constanta Vi pe unitate de timp (daca Vi e pozitiv acesta se misca spre +infinit, si daca e negativ se misca spre -infinit).
Daca pudge arunca hook-ul in punctul X0, acesta va prinde toti inamicii care sunt in intervalul [X0-d/2,X0+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
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.

Urmeaza N linii, fiecare avand 2 numere Pi, pozitia initiala a inamicului, si Vi, viteaza acestuia.

h2. Date de ieşire

h2. Restricţii

* $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.

* 1 <= N <= 100.000.
* 0 <= X, Y, X0 <= 10^8.
* 0 <= Pi <= 10^8, -10 <= Vi <= 10, pentru fiecare inamic.
* Pentru 20% din punctaj Vi = 0 pentru toti inamicii si 0 <= X, Y, X0, Pi <= 10^6.
* Pentru alte 20% din punctaj 1 <= N <= 1000 si 0 <= X, Y, X0, Pi <= 1000.
* Pentru alte 40% din punctaj 0 <= X, Y, X0, Pi <= 10^6.
* Pentru alte 20% din punctaj restrictiile initiale.

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

| 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

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

|
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") ==