Path Through the Mountains 2
The Earth's surface in a mountainous region can be depicted as a series of connected line segments. The endpoints of these segments are at the coordinates (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: walking along the Earth's surface (following the line segments) or constructing a bridge in the air to cross over. A bridge can only connect two vertices of the line segments; it cannot start or end anywhere other than a vertex, and it cannot go underground or through a mountain, though it may run along the Earth's surface in parts. The length of any single bridge cannot exceed R. Overall, the mage can build bridges with a total length not exceeding S. Once a bridge is crossed, it disappears. What is the shortest distance the mage must travel to reach point (x_N, y_N)?
Input
The input begins with a natural number N (2 ≤ N ≤ 64), followed by an integer R (0 ≤ R ≤ 10000) representing the maximum possible length of a single bridge, and an integer S (R ≤ S ≤ 10000) indicating the maximum total length of all bridges. Then, 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 each i from 1 to N-1, it holds that x_i < x_i+1.
Output
The output should be a single number representing the minimum length of the path the mage must travel (both on foot and via bridges). The result should be accurate to 5 decimal places.