题目描述

给定 $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$ 次切割后能够得到的最大区间数量。

1
3 3
1 3
2 4
1 4

Case #1: 7

提示

在给出的样例中，应在 $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 完成