310444: CF1834D. Survey in Class

D. Survey in Classtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Zinaida Viktorovna has $n$ students in her history class. The homework for today included $m$ topics, but the students had little time to prepare, so $i$-th student learned only topics from $l_i$ to $r_i$ inclusive.

At the beginning of the lesson, each student holds their hand at $0$. The teacher wants to ask some topics. It goes like this:

• The teacher asks the topic $k$.
• If the student has learned topic $k$, then he raises his hand by $1$, otherwise he lower it by $1$.

Each topic Zinaida Viktorovna can ask no more than one time.

Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.

Note that the student's hand can go below $0$.

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$ ($2 \le n \le 10^5, 1 \le m \le 10^9$) — the number of students and the number of topics, respectively.

Each of the next $n$ lines of each test case contain two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le m$) — the endpoints of the segment of topics that $i$-th student has learned.

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

Output

For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

ExampleInput

6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
3 5
1 1
3 3
5 5
4 7
1 7
1 3
3 3
4 5
2 4
1 3
2 4

Output

6
4
0
2
12
2

Note

In the first test case, Zinaida Viktorovna can ask the topics $5, 6, 7, 8$. Then the hand of the $2$-nd student will be at the height of $4$, and the hand of the $4$-th will be at the height of $-2$, that is, the difference will be equal to $6$.

In the second test case, you can ask about the topics $1$ and $3$. Then the hand of the $1$-st student will be at the height of $2$ and the hand of the $3$-rd student will be at the height of $-2$. So the difference will be $4$.

In the third test case, the difference between the highest and lowest hand will be $0$ for any set of topics asked.

In the fifth test case, you can ask all topics. Then the difference between the heights of the $1$-st and $3$-rd students' hands will be $12$.

**题目大意**：

Zinaida Viktorovna的历史课上共有n名学生，今天的作业包含m个主题。由于时间紧迫，第i名学生只学习了从l_i到r_i（含两端）的主题。课堂开始时，每位学生的手都举在0的位置。老师会提问一些主题，规则如下：

- 老师提问第k个主题。
- 如果学生学过这个主题，他把手举高1单位；如果没学过，则把手放低1单位。

每个主题Zinaida Viktorovna只能提问一次。注意学生的手位置可以低于0。需要找出在调查后，课堂中最高和最低的手之间可能的最大差距。

**输入数据格式**：

输入包含多个测试用例。第一行包含测试用例的数量t（1 ≤ t ≤ 10^4）。每个测试用例的第一行包含两个整数n和m（2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9），分别表示学生数和主题数。接下来n行，每行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ m），表示第i名学生学习的主题区间。所有测试用例的n之和不超过10^5。

**输出数据格式**：

对于每个测试用例，输出一个整数，表示调查后课堂中最高和最低的手之间可能的最大差距。

**示例**：

输入：
```
6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
2 4
1 3
2 4
```
输出：
```
6
4
0
2
12
2
```

**注意**：

- 在第一个测试用例中，可以提问主题5, 6, 7, 8。这样第二个学生的手会举到4的高度，而第四个学生的手会降到-2的高度，差距为6。
- 在第二个测试用例中，可以提问主题1和3。这样第一个学生的手会举到2的高度，而第三个学生的手会降到-2的高度，差距为4。
- 在第三个测试用例中，无论如何提问，最高和最低的手之间的差距都是0。
- 在第五个测试用例中，可以提问所有主题。这样第一个和第三个学生手的高度差为12。**题目大意**： Zinaida Viktorovna的历史课上共有n名学生，今天的作业包含m个主题。由于时间紧迫，第i名学生只学习了从l_i到r_i（含两端）的主题。课堂开始时，每位学生的手都举在0的位置。老师会提问一些主题，规则如下： - 老师提问第k个主题。 - 如果学生学过这个主题，他把手举高1单位；如果没学过，则把手放低1单位。 每个主题Zinaida Viktorovna只能提问一次。注意学生的手位置可以低于0。需要找出在调查后，课堂中最高和最低的手之间可能的最大差距。 **输入数据格式**： 输入包含多个测试用例。第一行包含测试用例的数量t（1 ≤ t ≤ 10^4）。每个测试用例的第一行包含两个整数n和m（2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9），分别表示学生数和主题数。接下来n行，每行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ m），表示第i名学生学习的主题区间。所有测试用例的n之和不超过10^5。 **输出数据格式**： 对于每个测试用例，输出一个整数，表示调查后课堂中最高和最低的手之间可能的最大差距。 **示例**： 输入： ``` 6 4 8 2 6 4 8 2 7 1 5 3 3 1 3 2 3 2 2 3 5 1 5 1 5 1 5 2 4 1 3 2 4 ``` 输出： ``` 6 4 0 2 12 2 ``` **注意**： - 在第一个测试用例中，可以提问主题5, 6, 7, 8。这样第二个学生的手会举到4的高度，而第四个学生的手会降到-2的高度，差距为6。 - 在第二个测试用例中，可以提问主题1和3。这样第一个学生的手会举到2的高度，而第三个学生的手会降到-2的高度，差距为4。 - 在第三个测试用例中，无论如何提问，最高和最低的手之间的差距都是0。 - 在第五个测试用例中，可以提问所有主题。这样第一个和第三个学生手的高度差为12。