Məsələlər
Козак Вус та відрізки
Козак Вус та відрізки
Нещодавно Козак Вус знайшов $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}
Giriş verilənləri #1
4 5 1 12 4 11 6 15 2 7
Çıxış verilənləri #1
4