407286: GYM102747 C Ремонт забора

C. Ремонт забораограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Забор состоит из $$$N$$$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают $$$L$$$ разных видов: шириной в 1 доску, в 2 доски, ... , в $$$L$$$ досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более $$$L$$$ подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие. Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какие наименьшее число щитов необходимо приобрести, чтобы починить весь забор.

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

Первая строка входных данных содержит целое число $$$L$$$ ($$$L > 0$$$) — максимальный размер щита. Во второй строке входных данных записано целое число $$$N$$$ ($$$N > 0$$$) — количество досок в заборе. Следующие $$$N$$$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.

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

Программа должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.

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

Решение, правильно работающее только для случаем когда числа $$$L$$$ и $$$N$$$ не превосходят 1000, будет оцениваться в 60 баллов.

В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $$$10^5$$$.

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

3
8
0
0
1
0
1
0
1
0

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

2

Примечание

Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.