题目背景

Mirko 用拖拉机采蘑菇。

题目描述

已知一个平面上 $n$ 个点，每个点的坐标可以用正整数 $X_i,Y_i$ 表示，求最小的 $ans$ 使前 $ans$ 个点中有至少 $k$ 个点处于同一行或同一列或同一与对角线平行的斜线。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行，每行两个正整数 $X_i,Y_i$。

输出格式

一个正整数 $ans$。如无解输出 $-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

提示

对于 $50\%$ 的数据，$1 \leq X_i,Y_i \leq 300$。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^6$，$1 \leq X_i,Y_i \leq 10^5$。

样例 1 解释：

。

译自 COCI 2014/2015 CONTEST #5