Description

Original source: Waterloo University 2002

In a certain region of the Arctic, there are $n$ villages, each represented by a pair of integer coordinates ($x, y$). To enhance communication, it is decided to establish a communication network among the villages. The communication tools can be either radio transceivers or satellite devices. All villages can be equipped with a radio transceiver, and all transceivers are of the same model. However, the number of satellite devices is limited, so only a subset of villages can be equipped with them.

Different models of radio transceivers have a parameter $d$. Two villages can communicate directly via radio if the distance between them does not exceed $d$. The larger the $d$ value, the more expensive the transceiver model. Villages equipped with satellite devices can communicate directly regardless of the distance between them.

Given $k$ satellite devices, write a program to determine how to allocate these $k$ devices so that the required $d$ value for the radio transceivers is minimized, ensuring that every pair of villages can communicate directly or indirectly.

For example, consider the following three villages:

Here, $|AB|= 10, |BC|= 20, |AC|= 10\sqrt{5}≈22.36$

If there are no satellite devices or only $1$ satellite device ($k=0$ or $k=1$), the smallest $d$ that satisfies the condition is $20$. This is because $A$ and $B$, and $B$ and $C$ can communicate directly via radio, while $A$ and $C$ can communicate indirectly through $B$ (i.e., messages are relayed from $A$ to $B$ and then from $B$ to $C$).

If there are $2$ satellite devices ($k=2$), they can be allocated to $B$ and $C$. The smallest $d$ can then be $10$, as $A$ and $B$ can communicate directly via radio, $B$ and $C$ can communicate directly via satellite, and $A$ and $C$ can communicate indirectly through $B$.

If there are $3$ satellite devices, $A$, $B$, and $C$ can all communicate directly via satellite, and the smallest $d$ can be $0$.

Input Format

The first line contains two space-separated integers $n$ and $k$;

The next $n$ lines each contain two integers, where the $i$-th line's $x_i, y_i$ represent the coordinates of the $i$-th village ($x_i, y_i$).

Output Format

A real number representing the smallest $d$ value, rounded to $2$ decimal places.

Sample 1

3 2
10 10
10 0
30 0

10.00

Data Range and Hints

For all data, $1\le n\le 500, 0\le x, y\le 10^4, 0\le k\le 100$.