문제
옛날 옛적에, GS왕국은 현명한 왕 준혁이에 의해 통치되고 있었어요.
17년간의 재위 기간 이후, 성공적인 수많은 전쟁과 능숙한 정치에 의해,
GS왕국은 2차원 좌표평면이 되었어요.
2차원 좌표평면 형태의 왕국은 경계가 없어 여행이 매우 간편해졌어요.
왕국의 큰 기념일이 다가왔어요! 왕국에는 사람들이 모일 수 있는 N개의 광장이 있어요.
준혁이는 그의 백성을 더 가까이서 살펴보고 싶었기에, 그는 광장 사이의 여행을 계획했어요.
준혁이는 방문하는 광장들에서 연설을 할 거에요.
처음에는, 준혁이는 p1 → p2 → ... → pn의 경로로 이동하고자 했어요.
그러나, 늙고 지친 준혁이는 너무나도 긴 여행을 견디지 못할거 같아요.
그래서, 준혁이의 보좌관 은수는 몇 개의 광장을 건너뛰기로 했어요.
새로운 여행 계획은 pi1 → pi2 → ... → pim의 경로로 표현돼요.
(1 = i1 < i2 < ... < im = n)
하지만, 준혁이는 pj에서 선분 pik -> pik+1 까지의 거리가 D를 초과할 경우 광장 j를 절대 건너뛰지 않을거에요. (ik < j < ik+1)
은수는 늙고 지친 준혁이를 걱정해서, 준혁이가 방문하는 광장의 수를 최소화시키고 싶어 해요.
여러분이 은수를 도와, 준혁이의 새로운 여행 경로를 찾는 것을 도와주세요.
입력
첫 번째 줄에는 N과 D가 공백으로 구분되어 주어져요.
N은 초기 여행 계획에서의 방문하는 광장의 개수,
D는 건너뛰는 광장에 대한 거리 조건을 뜻해요. (2 ≤ N ≤ 2,000, 1 ≤ D ≤ 1,000,000)
이어지는 N개의 줄은 광장들의 위치를 나타내요.
N개의 줄 중 i번째 줄에는 xi와 yi가 공백으로 구분되어 주어져요.
이는 pi가 (xi, yi)에 위치해있다는 뜻이에요. (-1,000,000 ≤ xi, yi ≤ 1,000,000)
출력
출력의 첫 번째 줄에, 준혁이가 방문하는 광장의 수의 최솟값을 출력해 주세요.
예제
5 2
2 6
8 2
14 2
12 9
13 8
3
입출력 예제의 원래 경로에요.
입출력 예제의 수정된 경로에요.
로그인해야 코드를 작성할 수 있어요.