COCI '14 Contest 5 #3 Traktor

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

Mirko got a super cool 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^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.


The first line of input contains the integers N (2 \le N \le 10^6) and K (2 \le K \le 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_i and Y_i (1 \le X_i, Y_i \le 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, output -1.


In test cases worth 50% of total points, it will hold 1 \le X_i, Y_i \le 300.

Sample Input 1

4 3
1 2
3 4
3 2
4 5

Sample Output 1


Explanation for Sample Output 1

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

Sample Input 2

7 4
3 1
2 2
4 1
3 2
2 3
1 4
1 3

Sample Output 2


Sample Input 3

5 2
1 1
2 1
1 2
1 3
1 4

Sample Output 3



There are no comments at the moment.