The Path Through the Mountains
The Earth's surface in a mountainous region can be depicted as a series of connected line segments. The vertices of these segments are located at points (x_1, y_1), (x_2, y_2), ..., (x_N, y_N), where x_i < x_i+1. A mountain mage starts at point (x_1, y_1) and aims to reach point (x_N, y_N). The mage can only travel on foot. He has two options: walk along the Earth's surface (i.e., follow the line segments) or construct a bridge to cross over. A bridge can connect two vertices of the line segments, but it must start and end at these vertices. The bridge cannot go underground or through a mountain, although it can partially follow the Earth's surface. The bridge's length cannot exceed R. The mage can build up to K bridges in total. Once a bridge is used, it disappears. What is the shortest distance the mage needs to travel to reach point (x_N, y_N)?
Input
The input begins with a natural number N (2 ≤ N ≤ 200), followed by a natural number K (1 ≤ K ≤ 100) representing the maximum number of bridges, and an integer R (0 ≤ R ≤ 10000) indicating the maximum possible length of a bridge. Next, the coordinates (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) are provided. All coordinates are integers, with absolute values not exceeding 10000, and for all i from 1 to N-1, x_i < x_i+1.
Output
The output should be a single number representing the minimum length of the path the mage must travel (including both walking and bridge crossings). The result should be presented with a precision of 5 decimal places.