선 맞춤

$2$차원 평면에 $x$좌표가 서로 다른 $n$개의 점이 주어진다. 이들을 $x$좌표 오름차순으로 정렬한 것을 $p_1$, $p_2$, $\cdots$, $p_n$이라고 하자. 각각의 인접한 두 점 $p_i$와 $p_{i+1}$사이를 선분으로 연결하면 모든 점을 지나는 꺾은선(polygonal line) L을 얻을 수 있다. 하지만 꺾은선 $L$은 $n-1$개의 선분으로 이루어진다. 우리는 이 꺾은선 $L$의 선분의 개수를 줄이는 대신에 $L$이 지나지 않는 점들은 $L$로부터 $y$축 방향거리가 $\epsilon$ 이내에 있도록 하고 싶다.

점들의 부분집합 $p_{i_1}$, $p_{i_2}$, $\cdots$, $p_{i_k}$ ($i_j < i_{j+1}$, $k \le n$)를 생각하자. 이 점들에서 인접한 두 점 $p_{i_j}$와 $p_{i_{j+1}}$을 선분으로 연결해서 얻은 꺾은선을 $M$이라고 하자. 여기서, $p_{i_1}=p_1$, $p_{i_k}=p_n$이어야 한다. 다시 말해서, 꺾은선 $M$은 첫째 점 $p_1$과 마지막 점 $p_n$은 지나야 한다. 위 부분집합에 속하지 않는 모든 점은 꺾은선 $M$으로부터 $y$축 방향거리가 $\epsilon$이내(거리가 $\epsilon$인 경우 포함)에 있어야 한다.

아래 그림은 두 점 $p_{i_j}$와 $p_{i_{j+1}}$ 사이의 모든 점이 $p_{i_j}$와 $p_{i_{j+1}}$을 연결하는 선분과 $y$축 방향거리가 $\epsilon$이내에 있음을 보여준다.

$n$개 점의 좌표와 $y$축 방향거리 제한 $\epsilon$이 주어질 때, 위의 조건을 만족하는 꺾은선 $M$을 구성하는 선분 개수 중 최소값을 계산하는 프로그램을 작성하라.

입력 형식

첫째 줄에 점들의 개수를 나타내는 정수 $n$과 $y$축 방향거리 제한을 나타내는 정수 $\epsilon$이 주어진다. ($1 \le n \le 10\,000$, $0 \le \epsilon \le 1\,000$)

이어지는 $n$개의 줄 각각에는 한 점의 좌표 $(x, y)$를 나타내는 두 정수 $x$와 $y$가 $x$좌표가 작은 것에서 큰 순서로 주어진다. ($-10^{6} \le x,y \le 10^{6}$) 모든 점의 $x$좌표는 서로 다르다.

출력 형식

한 줄에 위의 조건을 만족하는 꺾은선 $M$ 중에서 선분 개수의 최소값을 출력한다.

예제

4 1
1 2
2 3
3 2
4 -1

2

예제 설명

$(1, 2)$, $(3, 2)$, $(4, -1)$을 고르면 선분의 개수가 $2$개로 최소가 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설