Итан управляет станцией вакцинации, чтобы помогать людям бороться с сезонным гриппом. Он анализирует исторические данные, чтобы разработать оптимальную стратегию использования вакцины.
Пусть в конкретный день на станцию вакцинации придут \(n\) пациентов. Пациент с номером \(i\) придёт в момент времени \(t_i\). Каждого пациента можно попросить подождать не более \(w\) моментов времени, то есть \(i\)-й пациент может получить вакцину в моменты времени \(t_i, t_i + 1, \ldots, t_i + w\).
Вакцины поставляются в упаковках, каждая упаковка состоит из \(k\) доз. Каждому пациенту требуется ровно одна доза. Пакеты хранятся в специальном холодильнике. После того, как пачку вынули из холодильника и открыли, ее уже нельзя положить обратно. Время жизни вакцины вне холодильника составляет \(d\) моментов времени. Таким образом, если упаковка была вынута из холодильника и открыта в момент \(x\), дозы из этой упаковки можно использовать для вакцинации пациентов в моменты \(x, x + 1, \ldots, x + d\). В момент \(x + d + 1\) все оставшиеся неиспользованные дозы этой пачки выбрасываются.
Предположим, что на станции вакцинации достаточно персонала для проведения произвольного количества операций в каждый момент времени. Какое минимальное количество упаковок вакцин требуется для вакцинации всех \(n\) пациентов?
Выходные данные
Выведите одно целое число — минимальное количество упаковок с вакциной, необходимое для вакцинации всех \(n\) пациентов.
Примечание
В первом наборе входных данных первая упаковка может быть открыта в момент времени \(1\) для вакцинации пациента \(1\). Затем дозы из этой упаковки будут использованы в моменты времени \(2\) и \(3\) для пациентов \(2\) и \(3\) соответственно. Далее персоналу необходимо попросить пациентов \(4\) и \(5\) дождаться момента \(13\). В момент \(13\) персонал открывает вторую упаковку вакцины и обслуживает пациентов \(4\) и \(5\). Наконец, последний пациент приходит в момент \(18\) и сразу же получает последнюю дозу из второй упаковки, пока она ещё не испортилась.
Во втором наборе входных данных вакцина может быть использована только в тот момент времени, когда её достают из холодильника. Более того, все пациенты хотят быть обслужены именно в тот момент, когда они приходят. Это означает, что персонал должен открыть две упаковки в момент \(3\) и использовать пять доз для пациентов \(1\), \(2\), \(3\), \(4\) и \(5\). Из этих двух упаковок останется три дозы, но их нельзя использовать для пациента \(6\). Когда пациент \(6\) приходит в момент \(4\), персоналу необходимо открыть новую упаковку, чтобы использовать только одну дозу из неё.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8
|
2
3
2
3
1
|