Hide

# Problem FGopher II The gopher family, having averted the canine threat, must face a new predator.

The are $n$ gophers and $m$ gopher holes, each at distinct $(x, y)$ coordinates. A hawk arrives and if a gopher does not reach a hole in $s$ seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity $v$. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.

## Input

The input contains several cases. The first line of each case contains four positive integers less than 100: $n$, $m$, $s$, and $v$. The next $n$ lines give the coordinates of the gophers; the following $m$ lines give the coordinates of the gopher holes. All coordinates are decimal numbers between 0 and 100 with one digit after the decimal point. All distances are in metres; all times are in seconds; all velocities are in metres per second.

## Output

Output consists of a single line for each case, giving the number of vulnerable gophers.

Sample Input 1 Sample Output 1
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

1

Hide