#XSDCSPJ25042. 王老师的线段选取
王老师的线段选取
题目描述
现在王老师有一个长度为 m 的数组 。一开始,这个数组的每个元素都等于 0。
之后,王老师需要从给定的 n 条线段中选取一些(可以全选,也可以都不选)。
第 i 条线段的左端点为 ,右端点为 。选取一条线段之后,王老师会给 都加上 1。
定义 为数组的最大值, 为数组的最小值。
王老师的任务是最大化 。请求出这个最大值。
输入格式
第一行一个正整数 T,表示数据组数。
对于每一组数据,第一行输入两个正整数 ,分别表示可以选取的线段数和数组长度。 接下来 n 行,第 i 行输入两个正整数 ,表示第 i 条线段的左右端点。
输出格式
对于每一组数据,输出一行一个整数,表示 的最大值。
样例输入 1
3
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
样例输出 1
1
3
2
提示/说明
样例解释
对于第一组数据,只有一条线段可以选。选完之后的数组为 ,所以答案就是 。
对于第二组数据,可以选择所有线段,之后数组变为 ,所以答案是 。
对于第三组数据,可以只选择前三条线段,之后数组变为 ,答案是 。
数据范围
测试点编号 1 ~ 3 | | 4 ~ 6 | |
7 ~10 | | 11~13 | |
14 ~ 20| |
对于 100% 的数据,,单个测试点 。