eolymp
bolt
Try our new interface for solving problems
Problems

Way via mountains

Way via mountains

Time limit 2 seconds
Memory limit 64 MiB

The highlands' surface can be presented as a polygonal chain with vertices at the points (x_1, y_1), (x_2, y_2), ..., (x_N, y_N), moreover x_i < x_{i+1}. Ordinary mountain's magus staying at (x_1, y_1) wants to move to the point (x_N, y_N). He can move only afoot. He can walk on the surface of the Earth (along the polygonal chain). However, he also can create a bridge in the air and walk through it. The bridge can connect two vertices of the polygonal chain: the bridge should start and nish in some vertices of the polygonal chain and the bridge can't go underground (so it shouldn't form a tunnel in the mountain), but some points or segments of the bridge can touch the surface of the earth. The bridge can't be longer than R. Magus can't build more than K bridges. After passing a bridge, it disappears in the air.

What the minimum distance magus should pass to move to the point (x_N, y_N)?

Input data

The program should read firstly positive integer N (2N555); then a positive integer K (1K256) - the maximum number of bridges; then an integer R (0R10000) - maximum possible length of the bridge. Next, the coordinates (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). All coordinates are integers and aren't exceeding 10000 by absolute value. x_i < x_{i+1} is true for all i from 1 to N-1.

Output data

The program should print a single number - the minimum length of path magus have to pass (both on the ground and through the bridges). Print answer to within 6 digits after the decimal point.

Examples

Input example #1
5 2 5
0 0
2 2
3 -1
4 1
5 0
Output example #1
6.4787086646190746
Author Илья Порублёв
Source Летняя школа Севастополь 2013, Волна 1, День 2