TAXI  Taxi
Besides the well known unbelievable lordly major town's history there also current problems in this town. But to understand these problems you should know some facts from the unbelievable lordly major town's history.
Once upon a time the population of the unbelievable lordly major town grew so much that the citizens were in need of building new houses. As it was not allowed to erect houses outside the city wall they decided to found a new little town directly beside the main town. We will refer to this second town as the new unbelievable lordly major town. In the new unbelievable lordly major town all streets were built as straight lines intersecting at right angles at fixed distances (see picture below).
Knowing this we can leave the town's history and can focus on nowadays problems. One of these problems is directly connected to the "somnolent naggy festival" (SONAFE). Despite its name it's one of the town's most popular events and nearly everybody wants to get a ticket. To give everyone the same chance of getting one of the few tickets the place and time of the advance sale are kept secret until some minutes before the ticket counter opens. Once the opening of the ticket counter is disclosed (by radio to give everyone a fair chance) everyone interested in getting some tickets tries to get to the counter immediately.
One of the most profiting citizens of this ticket selling procedure is the new unbelievable lordly major town's taxi service owner. At the time of the radio announcement all over the town people ring up the taxi central and ask for a ride. The problem for the taxi central is that a lot of people ask for a ride at the same time and that the taxis have to pick up the people very quickly.
Your task is to help the taxi central finding out how many passengers can be transported to the ticket counter. You have to adhere to following constraints:
 each taxi can only take one passenger
 passengers always wait at intersections of roads
 at the time of the radio broadcast all taxis also wait at intersections
 the taxi has to reach the passenger within a given time limit (otherwise he will be too late to get a ticket)
Input
The first line contains the number of testcases k (k<=250). The first line of each testcase contains the number of persons p (1<=p<=400), the number of taxicabs t (1<=t<=200) the speed s (1<=s<=2000) of the taxis in meters per seconds and the time c to collect a person in seconds (1<=c<=1000000). The next p lines contains the position of the persons. The next t lines contain the position of the taxicabs in the city.
Output
For each testcase output the maximal number of persons that visit the party.
Example
Input: 1 2 3 10 40 2 5 5 2 2 3 4 1 4 4 Output: 2
hide comments
totallynotan:
20180315 22:54:32
:D that time limit tho 

vaibhavk31:
20170602 21:34:28
Wow MBM is great


bruzelee:
20170105 14:20:57
take care of that 200 meters 

SANYAM JAIN:
20160806 12:26:37
my 100th :) 

Superty:
20160731 15:45:01
Be careful! The distance between two adjacent intersections is 200m! 

minhthai:
20160220 03:57:21
if I divide the distance by speed to get the time, I get WA... 

sigma_poet:
20160110 12:40:12
What does this problem means??? English is poor... 

sigma_poet:
20160110 12:27:02
though 22s is enough, you know that spoj 's judging is slow slow slow ....... 

Augusto:
20150929 18:47:39
time limit should be a lot shorter :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150824 14:01:09
22s time limit is too relax :p 
Added by:  Simon 
Date:  20050620 
Time limit:  22s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL GOSU JSRHINO NODEJS OBJC PERL6 VB.NET 
Resource:  Ulm Algorithm Course SoSe 2005 