Path Through the Mountains 2#814
The Earth's surface in a mountainous region can be represented as a polyline. The vertices of this polyline are at points \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right), where x_i < x_{i+1} for each .
A mountain mage is located at \left(x_1, y_1\right) and wishes to reach \left(x_N, y_N\right). The mage can move:
By walking along the Earth's surface (along the given polyline).
By creating a bridge in the air, connecting two vertices of the polyline, and walking along it.
A bridge must satisfy the following:
It must start and end at the vertices of the polyline.
It cannot go underground (including passing through a mountain as a tunnel), but may overlap with the Earth's surface in some sections.
The length of any single bridge cannot exceed .
The total length of all bridges used cannot exceed .
After crossing a bridge, it disappears.
What is the minimum distance the mage must travel (walking both along the surface and on bridges) to reach the point \left(x_N, y_N\right)?
The input consists of:
An integer (2 \leq N \leq 64).
An integer (0 \leq R \leq 10000) — the maximum allowed length of one bridge.
An integer (R \leq S \leq 10000) — the maximum total length for the bridges.
Then, pairs of integers \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right).
All coordinates are integers with absolute value not exceeding . For every from to N-1, x_i < x_{i+1}.
Print a single number — the minimum length of the path the mage must take (walking along the polyline and via bridges). Output the answer with exactly digits after the decimal point.
Example 1