Antenna

A telecommunications company is building a wireless network in a city. To satisfy its contract, the signal must reach at least $K$ of the city's households. Because the cost grows with the antenna's range, the company wants to place a single antenna so that the range needed to cover at least $K$ households is as small as possible.

There are $N$ households, each at integer coordinates. The antenna may be placed at any point of the plane (its coordinates need not be integers), and its range may be any positive real number $R$. A household is covered when its Euclidean distance to the antenna is at most $R$.

Given the households and the integer $K$, determine the smallest range $R$ that lets a single antenna cover at least $K$ households.

The first line contains two integers $N$ and $K$ ($2 \le K \le N \le 500$) — the number of households and the minimum number that must be covered.

Each of the next $N$ lines contains two integers $X$ and $Y$ ($0 \le X, Y \le 10\,000$) — the coordinates of one household. No two households share the same coordinates.

Let $R$ be the smallest range that allows at least $K$ households to be covered. The value $R^2$ is always rational, because the optimal circle is fixed either by two households lying on a diameter or by three households lying on its boundary.

Output $R^2$ as an irreducible fraction in the form p/q, where $p$ and $q$ are integers, $q \ge 1$, and $\gcd(p, q) = 1$. Always print the denominator explicitly (for example, write 5/1 when $R^2 = 5$).

The figures below illustrate how a single circle of the minimum range covers the required households.