#J3036. 超级吸铁球

超级吸铁球

题目描述

小紫在玩一款益智游戏《超级吸铁球》。
在这款游戏中,每一关都有一定数量的球,你唯一能进行的操作就是选中平面上的任意一个球,然后以该球为中心,所有和该球的曼哈顿距离小于等于一个定值的球都会被吸引过来,因为无视碰撞体积,故范围内的所有球都会被吸引到中心点上。
一关的达成条件就是在限定的操作次数内,将所有的球都吸引到同一坐标。此外,这款游戏还有一个奖励机制,每一关都有一个理论上最少操作次数,只要你能够以最少操作次数完成本关,游戏就会奖励你限定的游戏皮肤。
这对于小紫来说诱惑太大,但是她并不是每一关都能达到最少操作次数,因此她想求助聪明的你来帮助她达成这个目标。
现在我们假设存在一个平面,平面上有n个位置均不同的球,坐标依次为(x1, y1), (x2, y2), ..., (xn, yn)。
同时我们指定一个最大吸引距离k。
你需要做的就是求出将所有点吸引到同一坐标的最少操作次数。游戏是必须有解的,但是本题不一定有解,对于无解情况,请你输出-1.

对于每次选中操作,例子如下:

如左图所示,我们选中了图中央的球,以该球为中心的红色菱形区域内的所有球,都会被吸引到同一个点,就如右图所示。

输入格式

第一行包含两个整数n和k,n表示球的数量,k表示最大吸引距离。
第2至n+1行,每行2个整数xi和yi,表示球i的坐标是(xi, yi)

输出格式

输出将所有球移动到同一坐标的最少操作次数,如果不可能,则输出-1.
3 2
0 0
1 1
2 2
1

提示

数据约定:

对于100%的数据:
2 ≤ n ≤ 104
0 ≤ k ≤ 1040