#XSDCSPJ25042. 王老师的线段选取

王老师的线段选取

题目描述

现在王老师有一个长度为 m 的数组 a1,a2,,ama_1 ,a_2 ,…,a_m 。一开始,这个数组的每个元素都等于 0。

之后,王老师需要从给定的 n 条线段中选取一些(可以全选,也可以都不选)。

第 i 条线段的左端点为 lil i​ ,右端点为 rir i 。选取一条线段之后,王老师会给 ali,ali+1,,aria_{l_i} ,a_{l_{i​+1}​} ,…,a_{r_i} 都加上 1。

定义 max(a)max(a) 为数组的最大值,min(a)min(a) 为数组的最小值。

王老师的任务是最大化 max(a)min(a)max(a)−min(a)。请求出这个最大值。

输入格式

第一行一个正整数 T,表示数据组数。

对于每一组数据,第一行输入两个正整数 n,mn,m,分别表示可以选取的线段数和数组长度。 接下来 n 行,第 i 行输入两个正整数 li,ril_i​ ,r_i​ ,表示第 i 条线段的左右端点。

输出格式

对于每一组数据,输出一行一个整数,表示 max(a)min(a)max(a)-min(a) 的最大值。

样例输入 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

提示/说明

样例解释

对于第一组数据,只有一条线段可以选。选完之后的数组为 [0,1,0][0,1,0],所以答案就是 10=11−0=1

对于第二组数据,可以选择所有线段,之后数组变为 [0,1,2,3,2,1,0,0][0,1,2,3,2,1,0,0],所以答案是 30=33−0=3

对于第三组数据,可以只选择前三条线段,之后数组变为 [3,2,1][3,2,1],答案是 31=23−1=2

数据范围

测试点编号 n∑n mm 1 ~ 3 | 20≤20 |100≤100 4 ~ 6 | 20≤20 |109≤10^9

7 ~10 |1000≤1000 |1000≤1000 11~13 |1000≤1000 |109≤10^9

14 ~ 20|105≤10^5 | 109≤10^9

对于 100% 的数据,1T103,1n105,1m109,1lirim1≤T≤10^3 ,1≤n≤10^5 ,1≤m≤10^9 ,1≤l_i​ ≤r_i​ ≤m,单个测试点 n105∑n≤10^5