Minimum Road Cost Across a River

A river is given as a polyline consisting of n points \((x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)\) connected sequentially. It is guaranteed that \(y_i < y_{i+1}\) for all \(1 \le i < n\).

You are to construct a road (also a polyline) from \((x_1,y_1)\) to \((x_n,y_n)\). The cost of a road is defined as

[ \text{cost} = a + T \cdot b, ]

where:

• a is the total Euclidean length of the road,
• b is the number of times the road crosses the river, and
• T is a given positive real number.

A road segment built exactly along the river (i.e. coinciding with a river segment) does not count as crossing.

The road can have arbitrarily many vertices (which you may choose to coincide with some of the river points). In an optimal plan, one may build some segments by jumping from one river point to another (thus not following the river) and each such segment may cross the river. In particular, for any chord joining two river points \(P_i\) and \(P_j\) (with \(i

[ f(P) = \det\bigl((x_j-x_i,;y_j-y_i),; (P - P_i)\bigr), ]

for each river vertex (P) (with the convention (f(P_i)=f(P_j)=0)), then for every consecutive pair of vertices (P_k, P_{k+1}) with (i < k < j), if both (f(P_k)) and (f(P_{k+1})) are nonzero and have opposite signs, the chord is considered to cross the river once. (If all intermediate vertices lie on one side of the chord — or are collinear with it — then no crossing is counted.)

Your task is to compute the minimum possible cost to build a road from \((x_1,y_1)\) to \((x_n,y_n)\).

inputFormat

The first line contains two numbers: an integer n (\(2 \le n\le \text{small}\)) and a positive real number T.

Then n lines follow. The \(i\)th line contains two real numbers \(x_i\) and \(y_i\) representing the coordinates of the \(i\)th river point. It is guaranteed that \(y_i < y_{i+1}\) for all \(1 \le i < n\).

outputFormat

Output a single real number: the minimum cost to build the road. Answers within an absolute or relative error of 1e-6 will be accepted.

sample

3 10
0 0
1 1
2 2

2.828427