Problem Description

EI is using a telescope to observe stars. There are $n$ stars in the sky, and each star has a 2D Cartesian coordinate $(x,y)$.

If the telescope is positioned at $(x_0,y_0)$, it can see all stars satisfying $(x_0-x)^2 + (y_0-y)^2 \le r^2$.

The telescope size $r$ can be adjusted. EI wants to know: if he wants to see at least $m$ stars, what is the minimum value to set $r$ to?

Input Format

The first line contains two positive integers $n,m$, representing the number of stars and the required number of stars to be seen.

The next $n$ lines each contain two integers $x,y$, representing the coordinate of one star.

It is guaranteed that all star coordinates are pairwise distinct.

Output Format

Output one line containing one positive real number, representing the minimum radius of the telescope.

Let your answer be $a$ and the standard answer be $b$. If $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$ (i.e., the absolute error or relative error does not exceed $10^{-6}$), then your answer is accepted.

4 3
0 0
1 1
2 3
3 3

1.41421356

Hint

For $100\%$ of the testdata, it is guaranteed that:

$2 \le m \le n \le 2000$.

$|x|,|y| \le 10^4$.

By: EntropyIncreaser.

Translated by ChatGPT 5