Description

Assume the coastline is an infinitely long straight line. One side is land, and the other side is ocean. Each island is a point on the sea surface. Radars must be installed on land (including the coastline), and each radar has the same scan range $d$. Your task is to build as few radar stations as possible so that all islands are within the scan range.

The data use the Cartesian coordinate system, with the coastline defined as the $x$ axis. The ocean is above the $x$ axis, and the land is below it.

Input Format

The first line contains $2$ integers $n$ and $d$, where $n$ is the number of islands and $d$ is the radar scan range.

Then follow $n$ lines, each containing two integers, the coordinates of an island.

Output Format

Output a single integer: the minimum number of radars required. If it is impossible to cover all islands, output -1.

3 2
1 2
-3 1
2 1

2

Hint

Sample 1 Explanation

Constraints

对于全部数据，$n\le1000$，$d \le 2\times 10^4$，$| x_i | \le 2 \times 10^6$，$0 \le y_i \le 2\times 10^4$。

Translated by ChatGPT 5