Problems
Way via mountains (small limits)
Way via mountains (small limits)
The highlands' surface can be presented as a polygonal chain with vertices at the points (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), ..., (\textbf{x_N}, \textbf{y_N}), moreover \textbf{x_i} < \textbf{x_\{i+1\}}. Ordinary mountain's magus staying at (\textbf{x_1}, \textbf{y_1}) wants to move to the point (\textbf{x_N}, \textbf{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 \textbf{R}. Magus can't build more than \textbf{K} bridges. After passing a bridge, it disappears in the air.
What the minimum distance magus should pass to move to the point (\textbf{x_N}, \textbf{y_N})?
\InputFile
The program should read firstly positive integer \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{42}); then a positive integer \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{23}) - the maximum number of bridges; then an integer \textbf{R} (\textbf{0} ≤ \textbf{R} ≤ \textbf{10000}) - maximum possible length of the bridge. Next, the coordinates (\textbf{x_1}, \textbf{y_1}), (\textbf{x_2}, \textbf{y_2}), ..., (\textbf{x_N}, \textbf{y_N}). All coordinates are integers and aren't exceeding \textbf{10000} by absolute value. \textbf{x_i} < \textbf{x_\{i+1\}} is true for all \textbf{i} from \textbf{1} to \textbf{N-1}.
\OutputFile
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 \textbf{6} digits after the decimal point.
Input example #1
5 2 5 0 0 2 2 3 -1 4 1 5 0
Output example #1
6.4787086646190746