Time limit
2s
Memory limit
128 MB
There are N field mice and M tunnels on a two-dimensional plane. Each mouse and each tunnel is located at one point on the plane, and each tunnel can hold at most one mouse.
A hawk will reach the ground S seconds from now. Every mouse can move V units of distance per second. If a mouse can reach a tunnel within S seconds, it can hide in that tunnel. A mouse that arrives exactly at S seconds is also considered safe.
The mice choose tunnels so that as few of them as possible are caught. Given the positions of the mice and tunnels, the time until the hawk arrives, and the mice's speed, find the minimum number of mice that will be caught.
The first line contains four integers N, M, S, and V. Each value satisfies 1 <= N, M, S, V <= 100.
The next N lines contain the x-coordinate and y-coordinate of each mouse. The following M lines contain the x-coordinate and y-coordinate of each tunnel.
Every coordinate is a real number whose absolute value is at most 1,000, and it may be given with up to three digits after the decimal point.
Print the minimum number of field mice that will be caught.