该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的羊腿切割机

文件读写

• 输入文件slicing.in
• 输出文件slicing.out

限制

• 2000ms
• 512MB

题目描述

徐老师为了切割羊腿，特意买了一台很大的羊腿切割机！

这台切割机有一个工作台，现在徐老师已经把一堆羊腿放在工作台上了

工作台是个二维平面，但是徐老师会把所有的羊腿放置到与工作台下边缘平行

工作台的两侧边缘上分别标注了坐标点 $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$ 只羊腿的放置位置

输出格式

对于每组测试数据，输出一行形为 Case #A: B 的答案 其中 $A$ 表示测试数据编号（从 $1$ 开始）, $B$ 表示徐老师能获得的最多羊腿块数

数据范围

对于所有数据满足：$1 \leq T \leq 10$

样例输入

2
3 1
1 3
2 4
1 4
3 3
1 3
2 4
1 4

样例输出

Case #1: 5
Case #2: 7 

样例解释

对于第二组测试数据，徐老师可以依次切割坐标 $2,3,4$ 可以获得最多的羊腿数量