Gopher II

Interview

Time limit1sMemory limit128 MB

Summary

Each gopher escapes if some hole within s*v metres is assigned to it, one gopher per hole; minimize the number of gophers left out by finding a maximum matching.

Level: Medium6 of 10
Topics: Graph, Union-find, Brute force, Geometry
Solved: No attempts yet

Problem

The gopher family, having averted the canine threat, must now face a new predator.

There are $n$ gophers and $m$ gopher holes, each located at a distinct $(x, y)$ coordinate. A hawk arrives, and any gopher that fails to reach a hole within $s$ seconds is vulnerable to being eaten. Each hole can shelter at most one gopher. Every gopher runs at the same speed $v$ . The gopher family needs an escape plan that minimizes the number of vulnerable gophers.

Since a gopher can travel at most $s \times v$ metres, a gopher can escape into a hole whenever the distance between them is at most $s \times v$ .

Input

The input consists of several test 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, and the following $m$ lines give the coordinates of the gopher holes. All distances are in metres, all times are in seconds, and all speeds are in metres per second. Input continues until end of file.

Output

For each case, output a single line containing the number of vulnerable gophers.

Examples4

Example 1

Input

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Expected output

Example 2
Input
```
1 1 100 1
0.0 0.0
0.5 0.5
```
Expected output
```
0
```
Example 3
Input
```
1 1 1 1
0.0 0.0
50.0 50.0
```
Expected output
```
1
```

Example 4

Input

Expected output