Задача №114094. Сауна
Макс очень любит ходить с друзьями в сауну. Сегодня он снова посетил сауну и взял с собой \(n\) своих друзей. Макс знает, что каждый друг посетит парилку ровно один раз, более того для каждого друга он знает отрезок времени, в которое он будет находится в парилке (предположим, что время измеряется в секундах с начала прихода в сауну). Макс хочет тоже сходить в парилку, причём тоже ровно один раз, однако он ещё не выбрал, когда именно ему это сделать.
Макс заботится о своей репутации. С точки зрения людей в бане, человек \(A\) круче человека \(B\), если \(A\) пришёл в парилку строго раньше \(B\), а ушёл строго позже \(B\) (тем самым показав, что он более стойкий). Назовём репутацией Макса количество людей, которые окажутся менее крутыми, чем он, минус количество людей, которые окажутся более крутыми, чем он.
Всему есть предел, в частности, Макс не может находиться в парилке больше чем \(t\) секунд. Помогите ему выбрать оптимальный отрезок времени для пребывания в парилке, чтобы значение его репутации было как можно больше.
Первая строка содержит два целых числа \(n\) и \(t\) (\(1 \leq n \leq 2 \cdot 10^5\), \(1 \leq t \leq 10^9\)) — количество друзей Макса и максимальное время, которое Макс может провести в парилке.
Каждая из следующих \(n\) строк содержит два целых числа \(l_i\) и \(r_i\) (\(0 \leq l_i \lt r_i \leq 10^9\)) — время прихода и ухода из парилки для каждого из друзей.
Обратите внимание, что несмотря на то, что все \(l_i\) и \(r_i\) являются целыми неотрицательными числами, границы отрезка времени, в течении которого Макс будет в сауне, не обязаны быть целыми или неотрицательными.
Выведите одно число — максимальную репутацию, которую Макс может получить, проведя в Сауне не более \(t\) секунд.
В первом примере, Макс может прийти в момент времени \(0.5\) и уйти в момент \(9.5\), и тем самым стать круче всех своих друзей.
Во втором примере, Макс не сможет стать круче всех своих друзей, но он, например, может прийти в момент \(0.3\) и уйти в \(7.1\), тогда он будет круче \(1\) и \(2\), но не друга \(3\). Впрочем, друг \(3\) не будет круче Макса, а значит ответ \(2\).
В третьем примере Макс может быть круче разве что друга \(2\), но в таком случае он точнее будет менее крутым, чем \(1\). Значит получить репутацию, большую \(0\) нельзя.
В четвёртом примере, Макс может получить репутацию \(0\) если придёт раньше или позже всех своих друзей.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
3 9 1 7 4 6 5 9
3
3 7 1 7 4 6 5 9
2
3 3 1 7 4 6 5 9
0
3 1 1 7 4 6 5 9
0