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

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

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