Забор состоит из $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 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.
## Входные Данные
Первая строка входных данных содержит целое число $L$ ($L > 0$) — максимальный размер щита. Во второй строке входных данных записано целое число $N$ ($N > 0$) — количество досок в заборе. Следующие $N$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.
## Выходные Данные
Программа должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.
## Пример
Входные данные3
8
0
0
1
0
1
0
1
0
Выходные данные2
## Примечание
Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.
## Система Оценки
Решение, правильно работающее только для случаем когда числа $L$ и $N$ не превосходят 1000, будет оцениваться в 60 баллов. В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $10^5$.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ denote the dimensions of a rectangular room.
**Constraints**
$ 1 \leq N, M \leq 1000 $
**Objective**
Determine whether the room of size $ N \times M $ can be completely tiled using L-shaped tiles, each covering exactly 3 unit squares.
**Condition for YES**
The tiling is possible if and only if:
$$
(N \cdot M) \equiv 0 \pmod{3} \quad \text{and} \quad \min(N, M) \geq 2
$$