开始: 2022-04-05 19:00:00

2022年4月双周赛(高级班)

结束: 2022-04-05 21:30:00
当前: 2025-1010-0303 09:02:28  类型:OI 状态:已经结束 
P4 : 贪心进阶-练习-雷达  
描述

有n个二维坐标点。

现在要在x轴上放置若干雷达,每个雷达的辐射半径都是d。

问至少需要几个雷达才能够辐射所有点,如果辐射不到所有的点,则输出-1。

输入

第一行一个整数n(1 \le n \le 1000)d(1 \le d \le 10000)

接下来n行,每行输入一个点的坐标。

坐标范围[-10000,10000]。

输出

输出一个整数表示答案。

样例

输入

3 2
1 2
-3 1
2 1

输出

2

输入

1 2
0 2

输出

1
提示

【样例1说明】

16889068213480.png