The Path Through the Mountains#808
The Earth's surface in a mountainous region can be represented as a connected polyline. The vertices of this polyline are located at points (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N), where x_i < x_{i+1}. A mountain mage starts at point (x_1, y_1) and wants to reach (x_N, y_N). The mage can only travel on foot, either walking along the polyline (the Earth's surface) or by constructing a bridge in the air to cross between vertices. A bridge can only connect two vertices of the polyline: it must start and end at a vertex and cannot go underground or pass through mountains (cannot be a tunnel), but it may partially follow the Earth's surface. The length of a bridge cannot exceed . The mage can build at most bridges in total. After traversing a bridge, it disappears. Find the minimum distance the mage must travel to reach (x_N, y_N) (walking on the surface and bridges).
The first line contains a natural number (2 \leq N \leq 200). The second line contains a natural number (1 \leq K \leq 100), the maximum number of bridges. The third line contains an integer (0 \leq R \leq 10000), the maximum possible length of a bridge. The next lines each contain two integers, the coordinates (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N). All coordinates are integers with absolute value at most . For all from to N-1, x_i < x_{i+1}.
Output a single number — the minimum length of the path the mage must travel (including along the ground and across bridges). Print the answer with a precision of decimal places.
Example 1