Problem Description

Mirko collects mushrooms with a tractor.

Given a plane with $n$ points, each point is represented by positive integers $X_i, Y_i$. Find the smallest $ans$ such that among the first $ans$ points, there are at least $k$ points on the same row, column, or diagonal (parallel to the main diagonals).

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 a single positive integer $ans$. If there is no solution, output $-1$.

Sample Input and Output

Sample Input #1

4 3
1 2
3 4
3 2
4 5

Sample Output #1

4

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

2

Notes

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

For $100\%$ of the test cases, $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

见题面 Input 部分

见题面 Output 部分