Description

For a sequence of real ordered pairs { <x₀, y₀>, <x₁, y₁>, …, <x_n, y_n> } satisfying x₀ < x₁ < … < x_n and any sequence of integers satisfying 0 = i₀ < i₁ < … < i_m = n, define

We wish to find the minimum possible value of .

Input

The input begins with the integers n and m (0 < m ≤ n ≤ 100), which are followed by the ordered pairs <x_i, y_i> (|x_i|, |y_i| ≤ 10⁴, 0 ≤ i ≤ n).

Output

The output contains only the minimum possible value of Δ. Any answers with a absolute error within 10⁻⁷ or a relative error within 10⁻⁹ are accepted.

1 1
0 0
1 1

0

Hint

sgn(x) is the sign function of x, which evaluates to for any non-zero x and 0 otherwise.

Source

POJ Monthly--2006.08.27, frkstyc