Козак Вус та відрізки#10486

Козак Вус та відрізки

2 секунди

256 мегабайтів

Легка

Нещодавно Козак Вус знайшов $n$ відрізків на координатній прямій. Відрізки задаються двома координатами $a_{i}$ a_i — початок відрізка та $b_{i}$ b_i — кінець відрізка.

Козак Вус хоче розмістити два нові відрізки довжини $m$ , щоб ці два відрізки не перетинались. Нехай $x$ — кількість відрізків, в яких повністю міститься перший відрізок. Аналогічно, $y$ — кількість відрізків, в яких повністю міститься другий відрізок.

Козак Вус хоче так розташувати ці $2$ відрізки, щоб число $x + y$ x+y було максимально можливим. Допоможіть йому знайти це число.

Зауважте, що один відрізок може повністю містити одночасно два ці нові відрізки.

Примітка 1. Нехай $k_{1}, k_{2}$ k_1, k_2 ( $k_{1} < k_{2}$ k_1 < k_2) — початки нових відрізків. Тоді ці відрізки не перетинаються, якщо $k_{1} + m \leq k_{2}$ k_1+m \le k_2.

Примітка 2. Новий відрізок з початком $k$ повністю міститься у відрізку $[l, r]$ [l, r], якщо $l \leq k$ l \le k та $k + m \leq r$ k+m \le r.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ( $1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m \leq 1 0^{8}$ 1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^8) — кількість відрізків та довжина нових відрізків.

Кожен з наступних $n$ рядків містить по два цілі числа $a_{i}, b_{i}$ a_i, b_i ( $1 \leq a_{i} < b_{i} \leq 1 0^{8}$ 1 \le a_i < b_i \le 10^8) — координати початку та кінця відповідного відрізка.

Вихідні дані

Виведіть єдине число — максимальне можливе значення виразу $x + y$ x+y.

Приклади

Приклад 1

Оцінювання

( $10$ балів): $n, m, a_{i}, b_{i} \leq 200$ n, m, a_i, b_i \le 200;
( $10$ балів): $n \leq 200$ n \le 200;
( $20$ балів): $n \leq 2000$ n \le 2000;
( $20$ балів): $n \leq 2 \cdot 1 0^{5}, m = 1$ n \le 2 \cdot 10^5, m=1;
( $40$ балів): без додаткових обмежень.