Survey in Class
Contest: Codeforces Round 879 (Div. 2)
Difficulty rating: 1900
Tags: brute force, data structures, greedy, implementation, sortings

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
6
4
0
2
12
2

Editorial:
Let's fix the students who will end up with the highest and lowest hands. Then, to maximize the difference, we can ask all the topics that the student with the highest hand knows. Then the second student will raise his hand for each topic in the intersection of their segments, and lower for each topic that only the first student knows. That is, the problem is to find $$$2$$$ segments $$$a$$$ and $$$b$$$ such that the value of $$$|a| - |a |\cap b|$$$ is maximal, since the answer is $$$2 \cdot (|a| - |a \cap b|)$$$.
The segment $$$b$$$ can intersect the segment $$$a$$$ in four ways: intersect the beginning of $$$a$$$, intersect the end of $$$a$$$, be completely inside $$$a$$$, or not intersect it at all. So, if in the answer segment $$$b$$$ intersects the beginning of $$$a$$$, then you can choose the segment with the minimal right end as the segment $$$b$$$ — the intersection of such a segment with $$$a$$$ will be no greater than the intersection of $$$b$$$ with $$$a$$$. Similarly, for the right end, you can select the segment with the maximal left end. If the answer has one segment in another, then you can consider the shortest segment in the set as the inner segment. If the segments in the answer do not intersect, then the segment does not intersect one of the "edge" segments.
Thus, to find the segment with which it has the minimum intersection for a given segment, you need to check 3 candidates: the shortest segment in the set, the segment with the minimal right end, and the one with the maximal left end. In total, to find the answer, you need to check $$$3n$$$ pairs of segments.