P16892 [GKS 2022 #F] Scheduling a Meeting

在 Google 安排会议并非易事。即使有了 Google 日历的帮助，Ada 也遇到了很多困难！ Ada 是 Google 的一名软件工程师，她需要为自己的新项目获得批准。为了获得批准，她需要与 $N$ 位技术主管中的至少 $K$ 位会面。 Ada 可以访问所有 $N$ 位技术主管的日历。对于每位技术主管，她可以看到他们所有已安排的会议。本题中的时间线可以看作 $D$ 个连续的小时，所有会议都在 $[0, D]$ 小时范围内，两端均为整数。已安排的会议（即使是同一个人的）可以重叠（在 Google 这点是出了名的！）。 Ada 需要安排一个长度为 $X$ 小时的会议，会议时间在 $[0, D]$ 小时区间内，两端也均为整数。至少要有 $K$ 位技术主管全程出席该会议，即他们的日历在整个会议持续时间内必须完全空闲。 不幸的是，可能已经无法找到这样的 $X$ 小时会议时间段。在这种情况下，Ada 需要说服一些技术主管取消他们现有的会议。 为了能让 Ada 与至少 $K$ 位技术主管会面，需要取消的最少已安排会议数量是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含 $4$ 个整数 $N$、$K$、$X$ 和 $D$。$N$ 表示技术主管的数量，$K$ 是 Ada 需要会面的最少技术主管人数，$X$ 是需要安排的会议时长，$D$ 是时间线 $[0, D]$ 小时区间的上界 —— 没有会议可以在 $D$ 之后结束。 每个测试用例的第二行包含一个整数 $M$，表示已安排会议的数量。 接下来 $M$ 行，其中第 $i$ 行包含 $3$ 个整数 $P_i$、$L_i$ 和 $R_i$。这些数字表示技术主管 $P_i$ 有一个安排在小时 $L_i$ 和 $R_i$ 之间的会议，不包含端点（即该会议可以看作一个开区间 $(L_i, R_i)$）。 注意，测试用例中的所有 $M$ 个会议是相互独立的，即使其中一些会议的开始和结束时间相同。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是为了能让 Ada 安排一个 $X$ 小时的会议并与至少 $K$ 位技术主管会面所需取消的最少已安排会议数量。 **关于时间格式的说明** 本题的时间线可以看作一个 $[0, D]$ 区间 —— 即 $D$ 个连续的小时，其中 $D$ 可能大于 $24$。 一个在区间 $(L, R)$ 内的会议表示会议在第 $L$ 小时开始时开始，在第 $R$ 小时开始时结束，覆盖了中间整个连续时间段（即区间是连续的）。开区间 $(L, R)$ 不包含端点。对于参加 Ada 安排会议的技术主管，Ada 的新会议可以与他们其他未取消的会议相邻 —— 即可以在另一个会议结束时恰好开始，或在另一个会议开始时恰好结束，或两者兼有。如果一位技术主管有任何其他未取消的会议与 Ada 的会议在任何时间点重叠，则该技术主管不能参加 Ada 的会议。 请参考样例测试用例的解释以获得更清晰的说明。

在样例 #1 中，Ada 需要安排一个 $2$ 小时的会议，并且至少有 $2$ 位技术主管参加。她可以在小时 $1$ 到 $3$ 之间安排这样的会议，让技术主管 #1 和 #3 参加。在这种情况下，无需取消任何现有会议。 在样例 #2 中，Ada 需要安排一个 $2$ 小时的会议，并且所有 $3$ 位技术主管都要参加。她可以在区间 $[0, 2]$ 安排这样的会议，这将需要取消会议 $2$ 和 $4$。另一种选择是在区间 $[1, 3]$ 安排会议。两种选择都需要取消 $2$ 场会议，这是可能的最小数量。 在样例 #3 中，Ada 需要安排一个 $3$ 小时的会议，并且至少有 $2$ 位技术主管参加。她可以在区间 $[0, 3]$ 安排会议，并与技术主管 #1 和 #3 会面。这将需要取消会议 $4$，这是此处的最优解。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le P_i \le N$。 对于所有 $i$，$0 \le L_i < R_i \le D$。 **测试集 1** $1 \le X \le D \le 8$。 $1 \le K \le N \le 10$。 $0 \le M \le 20$。 **测试集 2** $1 \le X \le D \le 10^5$。 $1 \le K \le N \le 10^5$。 $0 \le M \le 10^5$。 翻译由 DeepSeek V4 Pro 完成