题目描述

魔法少女小樱现在有$n$个区间。分别是$[l_1,r_1 ],[l_2,r_2 ],…,[l_n,r_n]$，保证$l_i<r_i$，且均为整数。

现在，小樱想对区间进行如下操作$m$次：

• 任意选择一个整数$x$，对于所有区间，若该区间满足$l_i<x<r_i$（ 注意不是 $≤$ ），将该区间分裂为两个区间$[l_i,x]$和$[x,r_i]$。

小樱希望最大化最后得到的区间数量。你的任务是帮助小樱计数她能够在这$m$次后获得的最多的区间数量。

为减少本题骗分做法通过，本题采取多组数据进行测试。

输入格式

第一行一个正整数$T$，表示本测试点共包含$T$组数据。

接下来每组数据，第一行包含两个整数$n,m$，分别表示区间的数量和允许的操作次数。

接下来$n$行，每行两个整数$l_i,r_i$表示区间的左右端点。

输出格式

对于每组数据，输出一行Case #x: y，其中$x$表示测试数据编号（从1开始编号），$y$表示本组测试数据答案。可参考样例进行理解。

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

Case #1: 5
Case #2: 7 

样例解释

对第一组数据：初始时为{[1, 3], [2, 4], [1, 4]}，可以进行一次操作。

对x=3进行操作最优，此时可以将后两个区间分裂，得到5个区间。

对于第二组数据：初始时为{[1, 3], [2, 4], [1, 4]}，可以进行三次操作。

以下是一种分裂到7个区间的方法：

第一次对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]}

第三次操作任意，可以发现本次操作不管对几操作都不会改变任何区间。

数据规模与约定

每组数据点10分，共10组数据。

大样例

大样例下载