Minimizing the Network Load Level in Wireless Sensor Networks

A wireless sensor network consists of a control center and n devices that collect data. Each device must send its data to the control center for processing. However, due to practical limitations, not every device can communicate directly with the control center. To cope with this, the network is structured as a tree. The control center is the root (and is not considered a device), and every device has exactly one parent (either the control center or another device). The load level of a device is defined as the number of its children devices, and the network load level is defined as the maximum load level among all devices.

Each device is placed in a 2D plane with coordinates (x, y), and the control center is located at the origin (0, 0). Two nodes (the control center or a device and another device) can communicate directly if the Euclidean distance between them is at most R. In addition, to ensure proper data routing, a device can only serve as the parent of devices that are farther from the control center than itself (i.e. if a device has distance d from the origin, it can only be the parent of devices whose distances are greater than d).

Your task is to design a tree network (i.e. assign a parent to every device) that connects all devices and minimizes the network load level. If it is impossible to connect all devices under the given communication range, output -1. In other words, you should determine the minimal possible maximum number of children among all devices in a valid configuration.

Note: The control center has no limitation on how many devices it can directly connect to, and its children are not counted when computing the load level.

inputFormat

The input consists of several lines:

• The first line contains two numbers: an integer n (the number of devices) and a number R (the communication range).
• Then follow n lines, each containing two integers x and y representing the coordinates of a device on the plane.

Constraints: It is guaranteed that 1 ≤ n and that all coordinates and R are such that a solution (or its impossibility) can be determined by your program.

outputFormat

Output a single integer: the minimized network load level – that is, the minimum possible maximum number of children that any device has in a valid tree network connecting all devices. If a valid network cannot be constructed under the given constraints, output -1.

sample

3 5
0 3
4 0
3 4

0