P7661 [COCI 2014/2015 #5] TRAKTOR
Background
Mirko uses a tractor to pick mushrooms.
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$.
Explanation/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](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf).
Translated by ChatGPT 5