Minimum Prefix for Aligned Points

Given a plane with \(n\) points where each point has positive integer coordinates \(X_i, Y_i\), find the smallest prefix length \(ans\) such that among the first \(ans\) points, there exist at least \(k\) points that lie on the same row, the same column, or on the same diagonal line parallel to the main diagonal (i.e. a line of the form \(y - x = c\)). If no such prefix exists, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(k\). Each of the next \(n\) lines contains two positive integers \(X_i\) and \(Y_i\) representing the coordinates of the \(i^{th}\) point.

outputFormat

Output a single integer representing the minimum prefix length \(ans\) for which the condition is satisfied. If no such prefix exists, output \(-1\).

sample

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

3