CF1884C.Medium Design

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.

数组 $a_1, a_2, \ldots, a_m$ 初始时全部为零。给定 $n$ 个两两互不相交的区间 $1 \le l_i \le r_i \le m$。你需要从中任选一个子集（特别地，该子集可以为空）。接着，执行以下操作：

• 对每个 $i = 1, 2, \ldots, n$，若区间 $(l_i, r_i)$ 被选入该子集，则对每个下标 $l_i \le j \le r_i$，将 $a_j$ 的值加 $1$（即 $a_j$ 被替换为 $a_j + 1$）；若区间 $(l_i, r_i)$ 未被选中，则数组保持不变。
• 接着（在处理完所有 $i = 1, 2, \ldots, n$ 后），计算 $\max(a)$，即数组 $a$ 中所有元素的最大值；类似地，计算 $\min(a)$，即数组 $a$ 中所有元素的最小值。
• 最后，定义所选区间子集的代价为 $\max(a) - \min(a)$。

请找出所有区间子集中所能达到的最大代价。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5$，$1 \le m \le 10^9$）——分别表示线段的数量和数组的长度。

每个测试用例接下来的 $n$ 行用于描述这些线段。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$）。保证所有线段两两互不相同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出给定线段集合的所有子集中最大的代价。

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

在第一个测试用例中，仅有一个可用的区间。如果我们不选择它，则数组为 $a = [0, 0, 0]$，该（空）区间子集的代价为 $0$。然而，如果我们选择这唯一的一个区间，则数组为 $a = [0, 1, 0]$，代价为 $1 - 0 = 1$。

在第二个测试用例中，我们可以选择所有区间：此时数组为 $a = [0, 1, 2, 3, 2, 1, 0, 0]$。代价为 $3 - 0 = 3$。