| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 8 | 8 | 4 | 100.000% |
Макс очень любит ходить с друзьями в сауну. Сегодня он снова посетил сауну и взял с собой $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 < r_i \leq 10^9$) --- время прихода и ухода из парилки для каждого из друзей.
Обратите внимание, что несмотря на то, что все $l_i$ и $r_i$ являются целыми неотрицательными числами, границы отрезка времени, в течении которого Макс будет в сауне, не обязаны быть целыми или неотрицательными.
Выведите одно число --- максимальную репутацию, которую Макс может получить, проведя в Сауне не более $t$ секунд.
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
В первом примере, Макс может прийти в момент времени 0ドル.5$ и уйти в момент 9ドル.5,ドル и тем самым стать круче всех своих друзей.
Во втором примере, Макс не сможет стать круче всех своих друзей, но он, например, может прийти в момент 0ドル.3$ и уйти в 7ドル.1,ドル тогда он будет круче 1ドル$ и 2ドル,ドル но не друга 3ドル$. Впрочем, друг 3ドル$ не будет круче Макса, а значит ответ 2ドル$.
В третьем примере Макс может быть круче разве что друга 2ドル,ドル но в таком случае он точнее будет менее крутым, чем 1ドル$. Значит получить репутацию, большую 0ドル$ нельзя.
В четвёртом примере, Макс может получить репутацию 0ドル$ если придёт раньше или позже всех своих друзей.