如今,每个人都拥有一部手机,甚至两三部。你可能知道它们名字的由来。手机是可以移动的(它们是“移动的”),并且它们使用无线连接到被称为基站(BTS,Base Transceiver Station)的固定站点。每个基站覆盖其周围的一个区域,该区域被称为小区(cell)。
捷克理工大学运行着一个实验性的私有 GSM 网络,在你目前所在的建筑顶部就有一个基站。由于基站的布局对网络覆盖至关重要,你的任务是编写一个程序,寻找基站的最佳位置。程序将给出“兴趣点”的坐标。目标是找到一个能够覆盖最多兴趣点的位置。假设基站可以覆盖所有距离其不超过给定距离 $R$ 的点。因此,小区的形状为圆形。
上图显示了八个兴趣点(小圆圈)和其中一个可能的最佳基站位置(小三角形)。对于给定的距离 $R$,不可能覆盖超过四个点。请注意,基站不需要放置在现有的兴趣点上。
输入格式
输入包含多个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $R$。$N$ 是兴趣点的数量,$1 \le N \le 2000$。$R$ 是基站能够覆盖的最大距离,$0 \le R < 10000$。接下来的 $N$ 行中,每行包含两个整数 $X_i, Y_i$,表示第 $i$ 个点的坐标,且 $|X_i|, |Y_i| < 10000$。所有点都是互不相同的,即没有两个点具有相同的坐标。
每个测试用例之后紧跟一个空行,然后开始下一个测试用例。最后一个测试用例之后是一行包含两个零。
位于圆边界上(距离恰好为 $R$)的点也被视为被覆盖。为了避免浮点数精度误差,输入的点在生成时满足以下条件:对于任何可以被半径为 $R + 0.001$ 的圆覆盖的点的子集 $S$,总是存在一个半径为 $R$ 的圆也能够覆盖它们。
输出格式
对于每个测试用例,输出一行,包含句子 "It is possible to cover M points.",其中 $M$ 是单个基站可以覆盖的最大兴趣点数量。
样例
输入样例 1
8 2 1 2 5 3 5 4 1 4 8 2 4 5 7 5 3 3 2 100 0 100 0 -100 0 0
输出样例 1
It is possible to cover 4 points. It is possible to cover 2 points.
说明
第一个样例输入对应的场景如上图所示,其中 $X$ 轴向右,$Y$ 轴向下。