406838: GYM102569 C Manhattan Distance

Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1 - x_2| + |y_1 - y_2|$$$.

There are $$$n$$$ pairwise distinct points on a plane. Consider all unordered pairs of these points, there are $$$\frac{n\left(n-1\right)}{2}$$$ such pairs in total. For every pair of points it is possible to calculate Manhattan distance between them. We don't ask you to calculate all such distances. Just output the $$$k$$$-th of them in increasing order.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100000, 1 \le k \le \frac{n\left(n-1\right)}{2}$$$) — the number of points and the sequence number of the distance you have to output.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8 \le x_i, y_i \le 10^8$$$) — the coordinates of the points. It is guaranteed that all $$$n$$$ points are pairwise distinct.

Output the $$$k$$$-th Manhattan distance in increasing order among all unordered pairs of points.

4 3
0 0
3 0
0 2
2 3

3

4 4
0 0
3 0
0 2
2 3

4

4 5
0 0
3 0
0 2
2 3

5