题目描述

在一个二维平面上有 n 个点，第 i 个点的坐标为 (xi, yi)。你需要使用若干个矩形来覆盖所有的点。

每个矩形的左下角固定在 (x1, 0)，右上角在 (x2, y2)，其中 x1 ≤ x2，y2 ≥ 0，并且必须满足 x2 - x1 ≤ w。

如果一个点位于矩形内部（包括边界上），则认为该点被矩形覆盖。

你的任务是：在确保每个点都 至少被一个矩形覆盖 的前提下，求最少需要多少个矩形。

输入格式

• 第一行包含两个整数 n 和 w，分别表示点的数量和矩形宽度的最大限制。
• 接下来 n 行，每行包含两个整数 xi 和 yi，表示一个点的坐标。

输出格式

• 输出一个整数，表示最少需要的矩形数目。

输入输出样例

输入样例 1

6 1
2 1
1 0
1 4
1 8
3 5
4 6

输出样例 1

2

样例 1 解释

一种可行的矩形放置方案：

• 第一个矩形：左下角 (1, 0)，右上角 (2, 8)
• 第二个矩形：左下角 (3, 0)，右上角 (4, 8)

输入样例 2

7 2
0 0
1 1
2 2
3 3
4 4
5 5
6 6

输出样例 2

3

样例 2 解释

一种可行的矩形放置方案：

• 第一个矩形：左下角 (0, 0)，右上角 (2, 2)
• 第二个矩形：左下角 (3, 0)，右上角 (5, 5)
• 第三个矩形：左下角 (6, 0)，右上角 (6, 6)

输入样例 3

2 0
2 3
1 2

输出样例 3

2

样例 3 解释

一种可行的矩形放置方案：

• 第一个矩形：左下角 (1, 0)，右上角 (1, 2)
• 第二个矩形：左下角 (2, 0)，右上角 (2, 3)

数据范围与约定

• 对于 100% 的数据：
  • 1 ≤ n ≤ 10⁵
  • 0 ≤ xi, yi ≤ 10⁹
  • 0 ≤ w ≤ 10⁹
  • 所有点坐标 (xi, yi) 互不相同