Cartesian

The Cartesian kingdom lies on a plane with Cartesian coordinates $(x, y)$. The kingdom extends infinitely in all directions.

The king wants to build a new palace. The palace is a square with sides parallel to the coordinate axes. The palace can be as large as needed, but the king cares more about its safety.

The kingdom has $n$ guard posts, and the $i$-th post is at $(x_i, y_i)$. The king can assign several guard groups to patrol the borders of the palace. The guards can only follow fairly simple orders. Each group must be assigned exactly two different posts. The group then patrols the smallest axis-parallel rectangle that contains those two posts. This rectangle may have zero area, for example when the two posts share an $x$ or a $y$ coordinate. To avoid confusion and conflicts, each post can be assigned to at most one group.

To feel safe enough, the king wants to form exactly $k$ guard groups. The palace must lie inside every rectangle patrolled by a group. That is, every point of the palace must be inside or on the boundary of each patrolled rectangle. Find the largest possible side length of a palace that can be built under these conditions.

The first line contains two integers $n$ and $k$ ($2 \le n \le 50000$, $1 \le k \le n/2$), the number of posts and the number of groups required.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^6 \le x_i, y_i \le 10^6$), the coordinates of a post.

It is guaranteed that no two posts are at the same point.

Print one number, the largest possible side length of the palace. If no palace with nonzero area satisfies the safety requirements, print $0$.

The pictures show the palace and guard routes for the first two examples. In the third example, the only possible route forms a segment, so a palace with nonzero side length cannot be obtained.