산악 하이킹

예제 $1$와 $2$에 나오는 산의 형태. 빨간색 선분은 너무 가팔라서 걸을 수 없다. 파란색 점선은 등산객들이 건설하는 다리이다.

산맥은 ($x_1$, $y_1$)부터 ($x_n$, $y_n$)까지의 $n$개 점으로 이루어지며, 여기서 $x_1 < x_2 < \dots < x_n$이다. 점 $i$와 점 $i+1$ 사이에는 선분이 있다.

몇몇 등산객이 산맥 전체를 횡단하려고 한다. 즉, 점 $1$에서 점 $n$까지 걸어가려고 한다. 하지만 기울기가 $d$보다 엄격히 큰 선분 위로는 걸을 수 없다. 여기서는 ($x_i$, $y_i$)와 ($x_j$, $y_j$)을 지나는 직선의 기울기를 다음과 같이 정의한다.

$$\frac{|y_i - y_j|}{|x_i - x_j|}$$

여기서 $|x|$은 $x$의 절댓값을 나타낸다.

하이킹이 가능하도록 등산객들은 산맥에 다리를 건설할 수 있다. 다리 역시 선분으로 표현되며, 항상 두 점 $i$와 $j$ 사이에 건설된다. 물론 다리의 기울기는 $d$보다 클 수 없으며, 또한 어느 지점에서든 산을 통과하는 다리는 건설할 수 없다.

하이킹이 가능하도록 건설해야 하는 다리들의 총길이의 최솟값을 구한다.

채점

여러 테스트 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$40$| $n \leq 100$

$2$ |$60$| 추가 제약 조건 없음.

첫째 줄에 정수 $n$과 부동소수점 수 $d$가 주어진다. ($2 \leq n \leq 1000$, $0 < d \le 10^5$). $d$은 소수점 이하 최대 세 자리의 정밀도로 주어진다.

이어지는 $n$개의 줄에는 각각 점 $i$의 좌표인 두 정수 $0 \leq x_i, y_i \le 10^6$가 공백으로 구분되어 주어진다. $x_i < x_{i+1}$임이 보장된다.

하이킹이 가능하도록 하는 데 필요한 다리들의 총길이의 최솟값을 부동소수점 수로 출력한다. 다리를 어떻게 건설하더라도 하이킹을 완료할 수 없다면 대신 $-1$을 출력한다.

절대 오차가 $10^{-3}$보다 작으면 정답으로 인정된다. 테스트 케이스의 결과는 수 $d$의 작은 변화에 영향을 받지 않음이 보장된다. (이는 부동소수점 수를 비교할 때 발생하는 정밀도 오차를 피하기 위함이다.)