The length of the road is N kilometers. Part of the road needs to be repaired. During the survey, the road was divided into N sections with a length of 1 kilometer, and for each section it was determined whether it needed repair or not, after which a road plan was drawn up, which marked the sections in need of repair.
Several contractors can be involved in the repair of the road. Each company can only repair a continuous section of the road. At the same time, due to the requirements of antimonopoly legislation, the length of the road fragment that is being repaired by one company should not exceed L kilometers (even if there are sections that do not need repair on the fragment that is being repaired by one company, the total length of this fragment should not exceed L kilometers) .
Determine the minimum number of contractors to be involved in the repair of the road.
The first line of the input contains an integer L (L > 0) — the maximum length of a road section that can be repaired by one company. The second line of the input contains an integer N (N > 0) — the length of the entire road. The next N lines contain one number each, equal to 0 or 1. The number 1 means that the corresponding section of the road needs repair, the number 0 — that the site does not require repair.
The program should output a single integer — the minimum number of contractors that must be involved in the repair of the road.
| Input |
Output |
Note |
3
8
0
0
1
0
1
0
1
0 |
2 |
First company can renovate section number 3, second company — sections 5 to 7. |