Minimum Radar Stations

Consider a scenario where the coastline is an infinitely long straight line. The land lies on one side, and the ocean on the other. Every island is represented as a point in the ocean. For the purpose of surveillance, radars must be installed on the land (including the coastline), and every radar has an identical scanning radius d.

Your task is to determine the minimum number of radars required so that each island is within the scanning range of at least one radar. Assume the Cartesian coordinate system where the coastline is the x-axis. The area above the x-axis represents the ocean, and the area below represents the land.

The scanning range of a radar is defined by a circle of radius d. However, the radar must be placed on or below the x-axis, so the effective coverage on an island at point \( (x_i, y_i) \) (with \(y_i > 0\)) is determined by whether there exists a point \( (x_r, 0) \) on the coastline (or further below) such that the Euclidean distance between \( (x_i, y_i) \) and \( (x_r, 0) \) is no more than \( d \). In mathematical terms, a radar placed at \( (x_r, 0) \) covers an island at \( (x_i, y_i) \) if and only if \[ (x_i - x_r)^2 + y_i^2 \le d^2. \]

Please note: If an island cannot be covered by any radar (i.e., \(y_i > d\)), then the problem has no solution and you should output -1.

inputFormat

The input consists of multiple test cases. Each test case begins with two integers \(n\) and \(d\), where \(n\) (\(1 \le n \le 1000\)) is the number of islands, and \(d\) (\(d > 0\)) is the scanning radius of each radar. This is followed by \(n\) lines, each containing two real numbers representing the coordinates \(x_i\) and \(y_i\) of an island. Note that \(y_i\) will be positive since islands are in the ocean.

The input terminates when \(n = -1\) and \(d = -1\).

outputFormat

For each test case, output a single line containing the minimum number of radars required to cover all islands. If it is not possible to cover all islands, output -1.

sample

4 5
1 2
2 4
-3 1
0 2
-1 -1

2