e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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