eolymp
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

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

Нещодавно Козак Вус знайшов $n$ відрізків на координатній прямій. Відрізки задаються двома координатами $a_i$ --- початок відрізка та $b_i$~--- кінець відрізка. Козак Вус хоче розмістити два нові відрізки довжини $m$, щоб ці два відрізки \textbf{не перетинались}. Нехай $x$ --- кількість відрізків, в яких повністю міститься перший відрізок. Аналогічно, $y$ --- кількість відрізків, в яких повністю міститься другий відрізок. Козак Вус хоче так розташувати ці $2$ відрізки, щоб число $x+y$ було максимально можливим. Допоможіть йому знайти це число. Зауважте, що один відрізок може повністю містити одночасно два ці нові відрізки. \textit{Примітка 1.} Нехай $k_1, k_2(k_1 < k_2)$~--- початки нових відрізків. Тоді ці відрізки \textbf{не перетинаються}, якщо $k_1+m \le k_2$. \textit{Примітка 2.} Новий відрізок з початком $k$ повністю міститься у відрізку $[l, r]$, якщо $l \le k$ та $k+m \le r$. \InputFile Перший рядок містить два цілі числа $n$ та $m$ ($1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^8$)~--- кількість відрізків та довжина нових відрізків. Кожен з наступних $n$ рядків містить по два цілі числа $a_i, b_i$($1 \le a_i < b_i \le 10^8$) --- координати початку та кінця відповідного відрізка. \OutputFile Виведіть єдине число --- максимальне можливе значення виразу $x+y$. \Scoring \begin{enumerate} \item ($10$ балів): $n, m, a_i, b_i \le 200$; \item ($10$ балів): $n \le 200$; \item ($20$ балів): $n \le 2000$; \item ($20$ балів): $n \le 2 \cdot 10^5, m=1$; \item ($40$ балів): без додаткових обмежень. \end{enumerate}
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4 5
1 12
4 11
6 15
2 7
Output example #1
4
Author Kostya Denisov