Radar Installation

Assume the coastline is an infinitely long straight line. Land lies on one side of the coastline and sea on the other. Each island is a single point located on the sea side. A radar installation placed on the coastline can cover a distance of $d$, so an island in the sea is covered by a radar if the distance between them is at most $d$.

We use a Cartesian coordinate system in which the coastline is the x-axis. The sea side is above the x-axis (positive $y$) and the land side is below it. Given the position of each island in the sea and the coverage distance $d$ of a radar, write a program to find the minimum number of radar installations needed to cover all islands. Each island's position is given by its x- and y-coordinates.

Figure A. A sample input of radar installations

The input consists of several test cases. The first line of each case contains two integers $n$ ($1 \le n \le 1000$) and $d$, where $n$ is the number of islands in the sea and $d$ is the coverage distance of a radar. This is followed by $n$ lines, each containing two integers that give the coordinates of one island. A blank line separates consecutive cases.

The input is terminated by a line containing a pair of zeros (0 0).

For each test case, print one line in the form Case x: y, where x is the test case number (starting from 1) and y is the minimum number of radar installations needed. If not all islands can be covered, print -1 in place of y.