Каждый вечер Виталик заводит n будильников, чтобы не проспать потом весь день. Каждый будильник звенит ровно одну минуту и характеризуется целым числом ai — номер минуты после полуночи, когда он срабатывает. Каждый будильник срабатывает в начале соответствующей минуты, и звенит ровно минуту.
Виталик точно проснётся, если за некоторые m подряд идущих минут сработают хотя бы k будильников. Обратите внимание, что Виталик учитывает только те будильники, которые начали звонить в данном промежутке времени. Будильники, которые начали звонить раньше, но продолжают звенеть в течении рассматриваемого промежутка Виталик не учитывает.
Виталик настолько устал, что хочет проспать весь день и не просыпаться. Определите минимальное количество будильников, которые нужно выключить Виталику, чтобы проспать весь следующий день. Считайте, что изначально все будильники включены.
Выходные данные
Определите минимальное количество будильников, которые нужно выключить Виталику, чтобы проспать весь следующий день.
Примечание
В первом примере Виталику достаточно выключить первый будильник, который звенит в минуту 3.
Во втором примере Виталику не нужно выключать ни одного будильника, так как ни за какие 10 подряд идущих минут не прозвенит 3 будильника.
В третьем примере Виталик должен выключить любые 6 будильников, чтобы продолжить сон.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
3 5 1
|
1
|
|
2
|
5 10 3
12 8 18 25 1
|
0
|
|
3
|
7 7 2
7 3 4 1 6 5 2
|
6
|
|
4
|
2 2 2
1 3
|
0
|