Description

Given $n$ points on a plane, each point has coordinates given by positive integers $X_i, Y_i$. Find the minimum $ans$ such that among the first $ans$ points, there are at least $k$ points lying on the same row, or the same column, or the same diagonal-parallel slanted line.

Input Format

The first line contains two positive integers $n, k$.

The next $n$ lines each contain two positive integers $X_i, Y_i$.

Output Format

Output one positive integer $ans$. If there is no solution, output $-1$.

4 3
1 2
3 4
3 2
4 5

4

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

6

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

2

Hint

For $50\%$ of the testdata, $1 \leq X_i, Y_i \leq 300$.

For $100\%$ of the testdata, $2 \leq k \leq n \leq 10^6$, $1 \leq X_i, Y_i \leq 10^5$.

Sample 1 Explanation:

.

Translated from COCI 2014/2015 CONTEST #5.

Translated by ChatGPT 5