Mushroom tractor

Mirko got a tractor for Christmas that can pick mushrooms. The mushrooms grow on a square meadow. In the coordinate plane that meadow is the square with lower left corner $(1, 1)$ and upper right corner $(10^5, 10^5)$.

At the start there is no mushroom on the meadow. Every second exactly one new mushroom grows on an empty spot, and $N$ of them grow in total. The $i$-th mushroom grows at second $i$.

Mirko wants to drive the tractor once and pick at least $K$ mushrooms. He starts at one of the lattice points of the meadow, and he moves only in a direction parallel to a side of the meadow or parallel to one of its diagonals. The tractor is so fast that the ride takes no time, and that speed also keeps him from turning during the ride. One ride therefore picks every mushroom on the line fixed by his starting point and his direction.

Find the smallest number of seconds after which Mirko can pick as many mushrooms as he wants.

The first line contains the number of mushrooms that will grow $N$ and the number of mushrooms Mirko wants to pick $K$. ($2 \le N \le 10^6$, $2 \le K \le N$)

Each of the next $N$ lines contains the coordinates $X_i$ and $Y_i$ of the $i$-th mushroom to grow. ($1 \le X_i, Y_i \le 10^5$) A mushroom grows only on an empty spot, so no two mushrooms have the same coordinates.

Print the smallest required number of seconds. If Mirko cannot pick $K$ mushrooms in one ride, print -1.

In the first example Mirko starts at $(1, 2)$ and rides toward the mushroom at $(4, 5)$.