안테나

한 통신 회사가 도시에 무선 통신망을 구축하려고 한다. 계약 조건을 만족하려면 신호가 도시의 가구 중 최소 $K$곳에 도달해야 한다. 안테나의 도달 범위가 넓어질수록 비용이 커지므로, 회사는 안테나 하나를 적절히 배치하여 최소 $K$개의 가구를 덮는 데 필요한 도달 범위를 최소로 만들고자 한다.

도시에는 $N$개의 가구가 있으며, 각 가구의 위치는 정수 좌표로 주어진다. 안테나는 평면 위의 임의의 점에 놓을 수 있고(좌표가 정수일 필요는 없다), 도달 범위 $R$은 임의의 양의 실수가 될 수 있다. 어떤 가구와 안테나 사이의 유클리드 거리가 $R$ 이하이면 그 가구는 신호가 도달한 것으로 본다.

가구들의 위치와 정수 $K$가 주어질 때, 안테나 하나로 최소 $K$개의 가구를 덮을 수 있는 가장 작은 도달 범위 $R$을 구하여라.

첫째 줄에 두 정수 $N$과 $K$가 주어진다 ($2 \le K \le N \le 500$). $N$은 가구의 수, $K$는 신호가 도달해야 하는 최소 가구 수이다.

다음 $N$개의 줄에 각각 두 정수 $X$와 $Y$가 주어진다 ($0 \le X, Y \le 10\,000$). 이는 한 가구의 좌표이다. 좌표가 같은 두 가구는 없다.

최소 $K$개의 가구를 덮을 수 있는 가장 작은 도달 범위를 $R$이라 하자. 최적의 원은 두 가구를 지름의 양 끝점으로 하거나 세 가구를 경계 위에 두는 원으로 정해지므로, $R^2$은 항상 유리수이다.

$R^2$을 기약분수 p/q 꼴로 출력한다. 여기서 $p$, $q$는 정수이고, $q \ge 1$이며, $\gcd(p, q) = 1$이다. 분모는 항상 명시하여 출력한다 (예: $R^2 = 5$이면 5/1로 출력).

아래 그림은 안테나 하나가 최소 도달 범위로 필요한 가구들을 덮는 모습을 나타낸 것이다.