cho.sh
Notes
Loading...

Field Mouse Escape

Time limit

2s

Memory limit

128 MB

Problem

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.

Input

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.

Output

Print the minimum number of field mice that will be caught.