408803: GYM103325 H Музей игровых автоматов

H. Музей игровых автоматовограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Один раз в год в городе Ч проводится день музеев для школьников. В музее советских игровых автоматов в этот день работало $$$k$$$ автоматов, время одной игры на каждом составляет $$$m$$$ минут. В одно и то же время на одном автомате не могут играть два человека.

Нам известно, что $$$n$$$ школьников заглядывали в этот день в музей: они записаны в протоколе в порядке прихода. Про каждого школьника $$$i$$$ нам известно время $$$x_i$$$, в которое он пришел в музей и время $$$y_i$$$, которое он был готов потратить на этот музей. Каждый школьник, заглянувший в музей, принимает решение: или ждать, когда освободится какой-нибудь автомат, после чего сыграть на нём одну игру, или же, если он не успевает сыграть в таких обстоятельствах, просто уйти.

В случае, когда два школьника претендуют на один и тот же автомат, преимущество имеет тот, кто стоит раньше в порядке протокола. Можете считать, что школьник $$$i$$$ может начать игру на автомате в тот же самый момент времени, когда последний школьник $$$j$$$, игравший на этом же автомате, закончил свою игру (то есть временем перехода к автомату и от него можно пренебречь).

Найдите число школьников, которым удастся поиграть в автомат.

Входные данные

В первой строке подается три числа — $$$n$$$, $$$k$$$ и $$$m$$$ $$$(1 \le n < 300\,000, 1 \le k, m \le 1000)$$$  — количество школьников в протоколе, количество автоматов, время игры на каждом автомате.

Следующие $$$n$$$ строк описывают протокол школьников. $$$i$$$-я из них содержит два числа — $$$x_i$$$ и $$$y_i$$$ $$$(0 \le x_i \le 1000, 1 \le y_i \le 1000)$$$ — время прихода и время ожидания школьника $$$i$$$. Протокол задан в порядке прихода школьников в музей.

Выходные данные

Выведите одно число — количество школьников, которые поиграли в этот день в музее.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text {Тесты из условия} & \\ \hline 1 & 15 & n < k & \text {}\\ \hline 2 & 25 & k = 1 & \text {}\\ \hline 3 & 30 & n \le 1000 & \text {}\\ \hline 4 & 30 & \text { Нет дополнительных ограничений }& \text {1, 2, 3}\\ \hline \end{array}$$$$$$

ПримерВходные данные

5 2 10
1 12
1 5
1 20
10 16
11 10

Выходные данные

4

Примечание

Тесты к этой задаче состоят из 4 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.