题目描述

你负责部署机器人从附近的小行星上收获 Kickium。机器人不是为团队合作而设计的，因此任何时刻只能有一个机器人在工作。一个机器人单次部署最多可以连续工作 $K$ 个时间单位，之后必须返回校准，无论这段时间内它实际用于收割的时间有多少。收割只能在特定的时间区间内进行，这些时间区间互不重叠。给定 $K$ 以及允许收割的时间区间，请问覆盖所有可收割时间所需的最少机器人部署次数是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行给出两个空格分隔的整数 $N$ 和 $K$：允许收割的时间区间数量，以及机器人单次部署后返回校准前可连续工作的最大时长。

接下来的 $N$ 行，每行包含一对空格分隔的整数 $S_i$ 和 $E_i$：第 $i$ 个区间的开始时间和结束时间。请注意，区间不包含 $E_i$ 时刻本身，因此例如区间 $(S_i = 2; E_i = 5)$ 的时长为 $3$ 个时间单位。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所需的最少机器人部署次数，使得每个区间内都有机器人在该时间段内进行收割。

2
3 5
1 5
10 11
8 9
3 2
1 2
3 5
13 14

Case #1: 2
Case #2: 3

提示

在样例 #1 中，我们在时刻 $1$ 部署机器人，它将在 $[1, 6)$ 时段内可用，但实际只在 $[1, 5)$ 时段内进行收割。之后我们在时刻 $6$ 再次部署机器人，它将在 $[6, 11)$ 时段内可用，这次部署覆盖了剩余的两个区间 $[8, 9)$ 和 $[10, 11)$。这里存在多种最优策略，例如我们也可以在时刻 $7$ 部署第二个机器人，它会覆盖 $[7, 12)$ 时段，从而同样收割区间 $[8, 9)$ 和 $[10, 11)$。

在样例 #2 中，我们在时刻 $1$ 部署机器人，它将在 $[1, 3)$ 时段内可用，但实际只收割 $[1, 2)$（因为 $[2, 3)$ 不属于任何区间）。之后我们在时刻 $3$ 部署机器人，它将在 $[3, 5)$ 时段内可用，并在该时段内收割区间 $[3, 5)$。第三次部署在时刻 $13$，机器人将在 $[13, 15)$ 时段内可用，但只收割区间 $[13, 14)$。因此需要 $3$ 次部署才能覆盖所有区间。

限制条件

$1 \le T \le 100$。

所有 $S_i$ 互不相同。

对于任意两个区间 $(S_i, E_i)$ 和 $(S_j, E_j)$，若 $S_i < S_j$，则 $E_i < S_j$。

测试集 1

$1 \le N \le 100$。

$1 \le K \le 100$。

$1 \le S_i < E_i \le 200$。

测试集 2

最多 $10$ 个测试用例满足 $100 < N \le 10^5$。

其余测试用例满足 $1 \le N \le 100$。

$1 \le K \le 10^9$。

$1 \le S_i < E_i \le 10^9$。

翻译由 DeepSeek V4 Pro 完成