Plot Approximation

We are given a plot consisting of n points in the plane: \(P_1, P_2, \ldots, P_n\). We want to approximate it with a new plot with at most m points (with \(m \le n\)) by partitioning the original plot into contiguous segments and contracting each segment into a single point.

In detail, the original sequence may be partitioned into \(s\) contiguous subsequences (with \(s \le m\)) as follows:

\[ (P_{k_0+1}, P_{k_0+2}, \ldots, P_{k_1}),\ (P_{k_1+1}, \ldots, P_{k_2}),\ \ldots,\ (P_{k_{s-1}+1}, \ldots, P_{k_s}) \]

where \(0=k_0 < k_1 < \cdots < k_s=n\). For each subsequence \( (P_{k_{i-1}+1}, \ldots, P_{k_i}) \) (for \(i=1,\ldots,s\)), a new point \(Q_i\) is chosen to represent it. The resemblance of the new plot \(Q_1, \ldots, Q_s\) to the original is measured as:

\[ \max_{i=1,\ldots,s} \Bigl( \max_{j=k_{i-1}+1,\ldots,k_i} d(P_j,Q_i) \Bigr), \]

where the distance \(d((x_1,y_1),(x_2,y_2))\) is defined by the formula:

\[ d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}. \]

Your task is to choose a partition (and optimal contraction points for each segment) so that the maximum distance from any original point to its corresponding contraction point is minimized. Due to floating point precision issues, a result is accepted if the computed resemblance is at most \(0.000001\) larger than the optimum value.

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(1 \le m \le n\)). Each of the next \(n\) lines contains two floating point numbers \(x\) and \(y\), representing the coordinates of a point \(P_i\).

outputFormat

Output a single floating point number, representing the minimum possible resemblance. The answer should be printed with at least 6 digits after the decimal point.

sample

2 1
0 0
1 0

0.500000

</p>