기지국 배치

휴대폰은 이동할 수 있으며(그래서 "모바일"이라고 부릅니다), 기지국(BTS, Base Transceiver Station)이라고 부르는 고정된 장치와 무선으로 통신합니다. 각 기지국은 자기 주변의 일정한 영역을 담당하며, 그 영역을 셀(cell)이라고 부릅니다.

한 연구실에서 건물 위에 기지국 하나를 올려 실험용 사설 GSM 망을 운영하고 있습니다. 기지국의 위치는 통신 커버리지에 매우 중요하므로, 기지국의 최적 위치를 찾는 프로그램을 작성하는 것이 여러분의 과제입니다. 프로그램에는 여러 개의 "관심 지점" 좌표가 주어집니다. 목표는 이 지점들을 가장 많이 덮을 수 있는 위치를 찾는 것입니다. 기지국은 자신으로부터 거리 R 이하에 있는 모든 지점을 덮을 수 있으므로, 셀은 원 모양이 됩니다.

예를 들어 관심 지점이 8개이고 적당한 거리 R이 주어졌을 때, 최적의 기지국 위치는 4개의 지점을 덮을 수 있으며 그보다 많은 지점을 덮는 것은 불가능할 수 있습니다. 기지국이 반드시 기존 관심 지점 위에 놓여야 하는 것은 아니라는 점에 유의하세요.

입력은 여러 개의 시나리오로 이루어집니다. 각 시나리오는 두 정수 N과 R이 담긴 줄로 시작합니다. N은 관심 지점의 개수로 1 ≤ N ≤ 2000 입니다. R은 기지국이 덮을 수 있는 최대 거리로 0 ≤ R < 10000 입니다. 그다음 N개의 줄이 이어지며, 각 줄에는 i번째 지점의 좌표인 두 정수 Xi, Yi가 담겨 있습니다(|Xi|, |Yi| < 10000). 모든 지점은 서로 다르며, 좌표가 같은 두 지점은 없습니다.

각 시나리오 뒤에는 빈 줄이 하나 오고, 그다음 시나리오가 시작됩니다. 마지막 시나리오 뒤에는 두 개의 0이 담긴 줄이 옵니다.

원의 경계 위에 정확히 놓인 지점(거리가 정확히 R인 지점)은 덮인 것으로 간주합니다. 부동소수점 오차를 피하기 위해, 입력 지점들은 다음을 만족하도록 선택됩니다: 반지름 R + 0.001인 원으로 덮을 수 있는 임의의 지점 부분집합에 대해, 항상 그 부분집합을 덮는 반지름 R인 원이 존재합니다.

각 시나리오마다 한 줄을 출력합니다: It is possible to cover M points. 여기서 M은 하나의 기지국으로 덮을 수 있는 관심 지점의 최대 개수입니다.