Migrated from Lutece 3133 CANOE

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：KDT、堆

この長い長い旅の その意味を

这个遥遥漫长的旅途的真正意义

希望をつなぐため

一切都是为了延续希望

天王寺瑚太朗望向浩瀚的星河，四散分布的群星让他想到了如下的问题。

在瑚太朗的视线范围内共有 $n$ 颗星星，为了描述每颗星星的位置，他假设天幕是一个二维平面，第 $i$ 颗星星的位置可以用坐标 $(x_i,y_i)$ 来表示。

对于任意无序二元组 $(i,j)(i\ne j)$ ，我们认为星星 $i$ 和星星 $j$ 构成了星对，定义该星对的遥远度为 $(x_i-x_j)^2+(y_i-y_j)^2$ （即二者欧氏距离的平方）。

现在瑚太朗想要知道，在所有的 $\frac{n\times (n-1)}{2}$ 个星对中，遥远度第 $k$ 大的值是多少。

Input

输入的第一行包括两个正整数 $n,k$ ，分别表示星星的数量以及想要知道的遥远度的排名。

接下来的 $n$ 行每行一个二元组 $(x_i,y_i)$ ，表示第 $i$ 颗星星的位置。

Output

输出一行一个整数，表示所有星对中遥远度第 $k$ 大的值。

Samples

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

9

Constraints

$1\le n\le 1\times 10^5,1\le k\le \min(100,\frac{n\times (n-1)}{2}),0\le x_i,y_i<2^{31}$

Note

数据保证所有星星的坐标在范围内等概率随机生成。

Resources

2024 UESTC ICPC Training for Data Structures