Tiny Room

Time limit2sMemory limit512 MB

Summary

Given N points and an H by W room, check whether the points can be rotated and moved to fit inside the room shrunk by R on every side.

Level: Medium6 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

You are an employee of Automatic Cleaning Machine (ACM) and a member of the development team of Intelligent Circular Perfect Cleaner (ICPC). ICPC is a robot that cleans up the dust of the places it passes through.

Your task is to inspect ICPC. The inspection checks whether the center of ICPC reaches all $N$ given points.

However, the laboratory may be too small to place all the points so that the entire body of ICPC stays inside the laboratory during the inspection. The laboratory is a rectangle of $H \times W$ , and ICPC is a circle of radius $R$ . Write a program that checks whether all the points can be placed in the laboratory by rotating and/or translating them while keeping the distance between every pair of points unchanged.

Input

The input consists of a single test case in the following format.

$N$ $H$ $W$ $R$
$x_1$ $y_1$
$\vdots$
$x_N$ $y_N$

The first line has four integers $N$ , $H$ , $W$ , and $R$ ( $1 \le N \le 100$ , $1 \le H, W \le 10^9$ , $1 \le R \le 10^6$ ). The following $N$ lines give the coordinates of the points that the center of ICPC must reach. The $(i+1)$ -th line has two integers $x_i$ and $y_i$ ( $0 \le x_i, y_i \le 10^9$ ), the x and y coordinates of the $i$ -th point. It is guaranteed that the answer does not change even if $R$ changes by $1$ .

Output

If all the points can be placed in the laboratory, print Yes. Otherwise, print No.

Examples4

Example 1
Input
```
4 20 20 1
10 0
20 10
10 20
0 10
```
Expected output
```
Yes
```
Example 2
Input
```
2 5 55 1
0 0
30 40
```
Expected output
```
Yes
```
Example 3
Input
```
2 5 49 1
0 0
30 40
```
Expected output
```
No
```
Example 4
Input
```
1 3 3 1
114 514
```
Expected output
```
Yes
```