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

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

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

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

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text {Тесты из условия} & \\ \hline 1 & 15 & n \lt 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}$$$$$$