D. Shortest Rope
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has a large pegboard with $$$n$$$ pegs. The $$$i$$$-th peg is located at position $$$(x_i, y_i)$$$.

He wants to run a rope from peg $$$1$$$ to peg $$$n$$$. To do this, he chooses a sequence of peg indices $$$$$$ 1 = i_1 \lt i_2 \lt \cdots \lt i_m = n, $$$$$$ and connects each consecutive pair of chosen pegs with a straight segment of rope.

However, Magikarp doesn't like to skip too many of his pegs, so no two consecutive indices can differ by more than $$$k$$$. Formally, this sequence must satisfy the condition that for every $$$1 \le t \lt m$$$, $$$$$$ i_{t+1} - i_t \le k. $$$$$$

The total rope length is the sum of the Euclidean distances between consecutive chosen pegs. Find the minimum possible total rope length.

Your answer will be accepted if it has absolute or relative error at most $$$10^{-6}$$$.

Input

The first line contains $$$n$$$ and $$$k$$$ $$$(2\le n\le 2\cdot 10^5, 1\le k\le 20)$$$ — the number of pegs and the maximum difference between consecutive indices.

The $$$i$$$th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(-10^9\le x_i,y_i\le 10^9)$$$ — the $$$x$$$ and $$$y$$$ coordinates of the $$$i$$$th peg.

Output

Output a single decimal — the minimum possible total rope length.

Example
Input
5 2
0 0
100 100
1 1
2 0
3 1
Output
3.4142135624
Note

How to print many decimals:

C++: 

cout << fixed << setprecision(10) << x << endl;

Java: 

System.out.printf("%.10f%n", x);

Python: 

print(f"{x:.10f}")
# or
print(format(x, ".10f"))