10645번 - TRAKTOR 다국어

Mirko got a supercool new tractor for Christmas that can even pick mushrooms! The mushrooms grow on a square-shaped meadow that can be placed in a coordinate plane so that its lower left edge is located at (1, 1) and its upper right edge at (10⁵, 10⁵).

Initially, there are no mushrooms on the meadow, but in total N will grow in a way that each second exactly one new mushroom grows on an empty space on the meadow.

Economical Mirko wants to ride his tractor only once and pick at least K mushrooms. His ride begins at one of the points on the meadow and he can move only in directions parallel to its sides or diagonals. Mirko’s tractor is super fast and travels great distances in negligible time. Because of the enormous speed, Mirko can’t make turns during the ride.

Help Mirko and determine the minimal number of seconds after which he can pick the wanted number of mushrooms.

The first line of input contains the integers N (2 ≤ N ≤ 10⁶) and K (2 ≤ K ≤ N), the number of mushrooms that will grow and the number of mushrooms Mirko wants to pick.

Each of the following N lines contains two integers Xi and Yi (1 ≤ Xi, Yi ≤ 10⁵), the coordinates of the ith mushroom grown on that meadow.

The first and only line of output must contain the required minimal number of seconds. If Mirko can’t pick K mushrooms in one ride, output -1.

Clarification of the first example: Mirko begins his ride at point (1, 2) and moves towards the mushroom located at (4, 5).