Bergsvandring

Figure 1: Bergets utseende i exemplen. De röda segmenten har för hög lutning för att gå på. De streckade blå linjerna är broar som vandrarna bygger.

En bergskedja består av $n$ punkter, ($x_1$, $y_1$) till ($x_ n$, $y_ n$), där $x_1 < x_2 < ... < x_ n$. Mellan punkt $i$ och punkt $i+1$ görs ett linjesegment.

Några vandrare vill ta sig över hela bergskedjan, dvs gå från punkt $1$ till punkt $n$. De kan dock inte gå på linjesegment om dess lutning är strikt större än $d$. Här definierar vi lutningen av linjen genom ($x_ i$, $y_ i$) och ($x_ j$, $y_ j$) som

där $|x|$ betecknar absolutvärdet av $x$.

För att göra vandringen möjlig kan de bygga broar i bergskedjan. En bro representeras också som ett linjesegment och byggs alltid mellan två punkter $i$ och $j$. En bro får självklart inte ha större lutning än $d$, och dessutom går det inte att bygga en bro som går igenom berget på något ställe.

Bestäm den minsta totala längden av de broar som behöver byggas för att vandringen ska vara möjlig.

Indata

På först raden står heltalet $n$ och flyttalet $0 < d \le 10^5$, separerade av mellanslag. De $n$ följande raderna innehåller två heltal $0 < x_ i, y_ i \le 10^5$, koordinaterna för punkt $i$, också separerade av mellanslag. Det är garanterat att $x_ i < x_{i+1}$.

Utdata

Skriv ut ett flyttal - minsta totala längden av broar som behövs för att göra vandringen möjlig. Om det är omöjligt att utföra vandringen oavsett hur man bygger broarna, skriv istället ut $-1$.

Precision

Ett svar på det här problemet kommer att räknas som korrekt om det absoluta felet är mindre än $10^{-3}$. Det är garanterat att resultatet för ett testfall inte påverkas av en liten ändring av talet $d$ (detta för att undvika precisionsfel vid jämförelser av flyttal).

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

10 1.2
0 0
2 2
3 0
4 1
5 0
6 1
7 0
8 0
9 2
11 0

5.06449510224598

11 1.6
0 0
2 3
4 3
5 5
6 1
7 7
8 3
9 5
12 2
13 3
15 1

9.231551362179038

3 1.9
0 0
10000 19999
30000 0

-1

7 0.8
0 0
50000 20000
120000 90000
170000 70000
180000 40000
240000 40000
310000 0

226157.73105863907