All submissions for this problem are available.Max is an avid sauna visitor. Today he's chilling in the sauna with $n$ friends. Max knows that each friend is going to visit the steam room exactly once, and the $i$-th friend is going to enter the steam room at time $l_i$, and leave at time $r_i$ (time is measured in seconds since the start of the visit). Max also wants to make a single visit to the steam room, but he can still choose his entering and leaving time. Max has his heat endurance reputation to maintain. In people's minds, a person $A$ is _cooler_ than another person $B$ if $A$ enters the steam room strictly earlier than $B$, but leaves strictly later then $B$ (thus proving that he's able to withstand heat longer). Depending on when Max enters and leaves the steam room, his _cred_ will be equal to the number of people that are less cool than Max, minus the number of people that are cooler than Max. Max has his limits, and so he cannot spend more than $t$ seconds in the steam room. Help Max determine the maximum cred he can get if he chooses entering and leaving times optimally. Note that Max's entering and leaving times do not have to be integers, and are even allowed to be negative. ###Input: - The first line of input contains a single integer $T$ - the number of test cases. $T$ descriptions of test cases follow. - The first line of each testcase contains two integers $n$ and $t$, denoting the number of Max's friends, and the maximum time Max can spend in the steam room, respectively. - The following $n$ lines describe entering and leaving time of Max's friends. The $i$-th of these lines contains two integers $l_i$ and $r_i$ - the entering and leaving time of the $i$-th friend. ###Output: For each test case, on a separate line print a single integer, the maximum cred Max can get while spending at most $t$ seconds in the steam room. ###Constraints - $1 \leq T \leq 2 \cdot 10^5$ - $1 \leq n \leq 2 \cdot 10^5$ - $1 \leq t \leq 10^9$ - $0 \leq l_i < r_i \leq 10^9$ - The sum of all $n$'s across all test cases in a single input will not exceed $2 \cdot 10^5$. ###Sample Input: 4 3 9 1 7 4 6 5 9 3 7 1 7 4 6 5 9 3 3 1 7 4 6 5 9 3 1 1 7 4 6 5 9 ###Sample Output: 3 2 0 0 ###EXPLANATION: In the first sample case Max may enter at time $0.5$ and leave at time $9.5$, thus becoming cooler than all of his friends. In the second sample Max cannot simultaneously be cooler than everyone, but, for example, if he enters at time $0.3$ and leaves at time $7.1$, he will be cooler than friends $1$ and $2$, and incomparable with friend $3$. In the third sample Max can only hope to be cooler than friend $2$, but in all such cases he will be out-cooled by friend $1$, thus he cannot gain positive cred. In the fourth sample, Max can get cred $0$ by entering and leaving before or after all of his friends.
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.