P16850 [GKS 2021 #D] Cutting Intervals

给定 $N$ 个区间。一个区间可以用两个正整数 $L_i$ 和 $R_i$ 表示：区间从 $L_i$ 开始，到 $R_i$ 结束，记作 $[L_i, R_i]$。区间可能不唯一，因此可能存在多个区间具有相同的 $L_i$ 和 $R_i$。 你最多可以进行 $C$ 次切割。一次在 $X$ 处的切割会将所有满足 $L < X$ 且 $X < R$ 的区间 $[L, R]$ 切开。将一个区间在 $X$ 处切开定义为将该区间分成两个区间：$[L, X]$ 和 $[X, R]$。注意，切割只能在整数点进行。此外，在区间的端点处切割（$X = L$ 或 $X = R$）没有效果，不会分裂区间。 你需要找出在最多 $C$ 次切割后，能够得到的最大区间数量。

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $C$，分别表示区间的数量和最多可以进行的切割次数。随后 $N$ 行，每行描述一个区间。 第 $i$ 行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 个区间。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在最多 $C$ 次切割后能够得到的最大区间数量。

在给出的样例中，应在 $2$ 和 $3$ 处进行切割，以获得最多的区间数量。 第一次在 $2$ 处切割后，区间变为 $\{[1, 2], [2, 3], [2, 4], [1, 2], [2, 4]\}$。 第二次在 $3$ 处切割后，区间变为 $\{[1, 2], [2, 3], [2, 3], [3, 4], [1, 2], [2, 3], [3, 4]\}$。 可以看出，没有区间可以再被切割，因此答案为 $7$。 ### 限制条件 内存限制：$1$ GB。 $1 \le T \le 100$。 **测试集 1** $1 \le N \le 500$。 $1 \le C \le 10^5$。 对于所有 $i$，$1 \le L_i < R_i \le 10^4$。 **测试集 2** $1 \le N \le 10^5$。 $1 \le C \le 10^{18}$。 对于所有 $i$，$1 \le L_i < R_i \le 10^{13}$。 翻译由 DeepSeek V4 Pro 完成