徐老师的羊腿切割机
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师为了切割羊腿，特意买了一台很大的羊腿切割机！这台切割机有一个工作台，现在徐老师已经把一堆羊腿放在工作台上了
工作台是个二维平面，但是徐老师会把所有的羊腿放置到与工作台下边缘平行
工作台的两侧边缘上分别标注了坐标点 $1,2,3 \dots$
现在徐老师将 $n$ 只羊腿放置在了工作台上，第 $i$ 只羊腿会放在横向第 $i$ 行上，并且两端刚好对齐工作台的坐标点 $x,y(x < y)$
例如有 $3$ 只羊腿，分别对齐的坐标点为：$[1,3],[2,4],[1,4]$
如下图用 $-$ 表示羊腿，这里是上述 $3$ 只羊腿的摆放形状
```
1 -----
2 -----
3 -------
1 2 3 4 5
```
每次切割时徐老师会设定一个坐标点 $a$，切割机将从上往下把所有经过的羊腿全部切开
例如上述例子，设定坐标点 $3$ 进行切割，显然这次切割对于三个羊腿将会造成：
1. 刚好经过 $1$ 号羊腿的右端点，所以不会切割 $1$ 号羊腿
2. 会将 $2$ 号羊腿 $[2,4]$ 切割成 $[2,3],[3,4]$ 两块
3. 将$3$ 号羊腿 $[1,4]$ 切割成 $[1,3],[3,4]$ 两块
那么这一次切割后徐老师将拥有 $5$ 块羊腿
现在徐老师将会进行 $m$ 次切割，他想获得尽可能多的块数，该如何切割？最多能切出几块羊腿？
输入格式
本题采用多组测试数据第一行一个整数 $T$ 表示测试数据数量，接下来对于每组测试数据有
第一行包含两个整数 $n,m$ 表示羊腿数量和切割次数
接下来 $n$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 只羊腿的放置位置
| 测试点编号 | $T,n,m$ | $x_i,y_i$ |
|:---:|:---:|:---:|
|$1 \sim 3$ | $1 \leq n,m \leq 10$ |$1 \leq x_i < y_i \leq 50$|
|$4 \sim 7$ | $1 \leq n,m \leq 10^3$ |$1 \leq x_i < y_i \leq 10^5$|
|$8 \sim 10$| $1 \leq n \leq 10^5, 1 \leq m \leq 10^{18}$ | $1 \leq x_i < y_i \leq 10^{12}$|
对于所有数据满足：$1 \leq T \leq 10$
输出格式
对于每组测试数据，输出一行形为 `Case #A: B` 的答案其中 $A$ 表示测试数据编号（从 $1$ 开始）, $B$ 表示徐老师能获得的最多羊腿块数
样例
2
3 1
1 3
2 4
1 4
3 3
1 3
2 4
1 4Case #1: 5
Case #2: 7 提示
对于第二组测试数据，徐老师可以依次切割坐标 $2,3,4$ 可以获得最多的羊腿数量23CSP-S秋季提高组模拟赛(9)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-4 21:15
- 结束于
- 2023-10-4 23:15
- 持续时间
- 2 小时
- 主持人
-
huangzhe
- 参赛人数
- 2
