\(5^{th}\) round, January \(17^{th}\) 2015
Mirko got a supercool new tractor for Christmas that can even pick mushrooms! The mushrooms grow
on a squa\(re-sh\)aped 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^{5}\), \(10^{5}\)).
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.

In test cases worth 50% of total points, it will hold 1 ⩽\(X\)\(i\), Y\(i\) ⩽300.

The first line of input contains the integers \(N\) (2 ⩽\(N\) ⩽\(10^{6}\)) 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 \(X@@RISE_MATH_BLOCK_0@@i\) (1 ⩽\(X\)\(i\), Y\(i\) ⩽\(10^{5}\)), the coordinates of
the \(i\)^{th} 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, outp\(ut -1\).

생성자가 기록되지 않았습니다.

출처 COCI 2014/2015 Contest 5