Do zdobycia pierwszego stopnia w harcerstwie (jedna belka) Jaś potrzebował kolejnej sprawności, mianowicie "Gimnastyk", która polegała na jak najszybszym
pokonaniu wyznaczonych odcinków drogi i przeniesieniu n (1 <= n <= 100000) przedmiotów pomiędzy ustalonymi punktami.
Ponieważ nie wszystkie dzieci były jednakowo
sprawne fizycznie, zastępowy utrudnił nieco zabawę projektując specjalny tor przeszkód pokazany na rysunku.
Cały obszar podzielony został na trzy części: obszar na lewo od odcinka specjalnego, obszar pomiędzy rozpiętymi linami, zwany
odcinkiem specjalnym oraz obszar na prawo od odcinka specjalnego. Zadaniem uczestnika
konkursu, który startuje z punktu zbiórki znajdującego na prawo od lin, jest zabrać przedmioty znajdujące sie po lewej stronie i zanieść je do punktu zbiórki po prawej stronie. Jaś odnosi przedmioty po kolei, tzn. gdy odniesie pierwszy, idzie po nastepny, itd...
Pokonując obszar o szerokości
d
pomiędzy równoległymi linami, czyli odcinek specjalny, uczestnik może
poruszać się wyłącznie prostopadle do lin stylem "na czworakach" z prędkością 1 [m/s] (nie ma dużych różnic pomiędzy uczestnikami), w pozostałych obszarach może biegać z prędkością
v [m/s]
(1 <= v <= 1000) (różnice pomiędzy uczestnikami mogą być znaczne).
Należy ustalić ile maksymalnie przedmiotów może przenieść Jaś zakładając, że dysponuje ograniczonym czasem
t [s]
(1 <=
t <= 10000000). Liny są rozpięte równolegle do osi OY w punktach
X o współrzędnych 0 oraz
d
(
d >= 0). Punkt zbiórki jest jeden i znajduje się w punkcie
wx wy (d <=
wx <= 1000,
-1000 <=
wy <= 1000), natomiast współrzędne położenia przedmiotów (kilka przedmiotów może znaleźć się w jednym miejscu) mają postać
rx ry
(-10000 <=
rx <= 0, -10000 <=
ry <= 10000). Zakładać będziemy, że wszystkie wartości są całkowite.
Testy podzielone są na dwie grupy:
- testy 1-5 (za 1 punkt): d = 0,
- testy 6-10 (za 2 punkty): brak dodatkowych ograniczeń.
Wejście
W pierwszej linii podana została liczba przedmiotów n, czas t, szerokość d, współrzędne wx wy oraz prędkość
v. W kolejnych n liniach podane zostały współrzędne rx ry przedmiotów.
Wyjście
Na wyjściu należy podać jak największą liczbę przedmiotów, które Jaś zdoła zebrać w czasie t zgodnie z przedstawionymi regułami.
Przykład 1
Wejście:
6 10 0 5 2 10
-2 -3
-5 9
-6 -10
-5 -3
0 -1
-7 -5
Wyjście:
4
Przykład 2
Wejście:
5 20 2 3 2 10
0 -7
-5 -5
-2 4
-4 -9
-4 -9
Wyjście:
3