Description

Given the coordinates of $N$ points in the plane, find the $K$-th farthest pair under the Euclidean distance.

The Euclidean distance between two points $P(x_1,y_1)$ and $Q(x_2,y_2)$ is defined as $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Input Format

The first line contains two integers $N,K$ separated by a space.

The next $N$ lines each contain two integers $X,Y$, representing the coordinates of a point.

Output Format

Output a single integer on the first line, which is the square of the distance of the $K$-th farthest pair (it is guaranteed to be an integer).

10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

9

Hint

For $100\%$ of the testdata, $N \le 100000,1 \le K \le 100,K \le \dfrac {N(N-1)}{2},0 \le X,Y < 2^{31}$.

Translated by ChatGPT 5