310771: CF1884C. Medium Design

C. Medium Designtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The array $a_1, a_2, \ldots, a_m$ is initially filled with zeroes. You are given $n$ pairwise distinct segments $1 \le l_i \le r_i \le m$. You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:

• For each $i = 1, 2, \ldots, n$, if the segment $(l_i, r_i)$ has been selected to the subset, then for each index $l_i \le j \le r_i$ you increase $a_j$ by $1$ (i. e. $a_j$ is replaced by $a_j + 1$). If the segment $(l_i, r_i)$ has not been selected, the array does not change.
• Next (after processing all values of $i = 1, 2, \ldots, n$), you compute $\max(a)$ as the maximum value among all elements of $a$. Analogously, compute $\min(a)$ as the minimum value.
• Finally, the cost of the selected subset of segments is declared as $\max(a) - \min(a)$.

Please, find the maximum cost among all subsets of segments.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$) — the number of segments and the length of the array.

The following $n$ lines of each test case describe the segments. The $i$-th of these lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le m$). It is guaranteed that the segments are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the maximum cost among all subsets of the given set of segments.

ExampleInput

6
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
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789

Output

1
3
2
3
4
4

Note

In the first test case, there is only one segment available. If we do not select it, then the array will be $a = [0, 0, 0]$, and the cost of such (empty) subset of segments will be $0$. If, however, we select the only segment, the array will be $a = [0, 1, 0]$, and the cost will be $1 - 0 = 1$.

In the second test case, we can select all the segments: the array will be $a = [0, 1, 2, 3, 2, 1, 0, 0]$ in this case. The cost will be $3 - 0 = 3$.

题目大意：
一个长度为m的数组a，初始值全为0。给定n个两两不同的线段，每个线段的范围是1到m。你可以选择任意一个线段子集（包括空集）。对于每个选中的线段，将其范围内的数组值增加1。最后计算数组中的最大值和最小值之差，即为所选线段子集的成本。要求找出所有线段子集中成本的最大值。

输入数据格式：
第一行包含一个整数t，表示测试用例的数量。每个测试用例的第一行包含两个整数n和m，分别表示线段的数量和数组的长度。接下来n行，每行包含两个整数li和ri，表示一个线段的左右端点。所有线段两两不同。

输出数据格式：
对于每个测试用例，输出一个整数，表示所有线段子集中成本的最大值。

示例输入输出：
输入：
6
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
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789

输出：
1
3
2
3
4
4题目大意： 一个长度为m的数组a，初始值全为0。给定n个两两不同的线段，每个线段的范围是1到m。你可以选择任意一个线段子集（包括空集）。对于每个选中的线段，将其范围内的数组值增加1。最后计算数组中的最大值和最小值之差，即为所选线段子集的成本。要求找出所有线段子集中成本的最大值。 输入数据格式： 第一行包含一个整数t，表示测试用例的数量。每个测试用例的第一行包含两个整数n和m，分别表示线段的数量和数组的长度。接下来n行，每行包含两个整数li和ri，表示一个线段的左右端点。所有线段两两不同。 输出数据格式： 对于每个测试用例，输出一个整数，表示所有线段子集中成本的最大值。 示例输入输出： 输入： 6 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 7 6 2 2 1 6 1 2 5 6 1 5 4 4 3 6 6 27 6 26 5 17 2 3 20 21 1 22 12 24 4 1000000000 2 999999999 3 1000000000 123456789 987654321 9274 123456789 输出： 1 3 2 3 4 4