Rainbow Bowl Ranges

Time limit2sMemory limit2048 MB

Summary

Given n bowls in a circle and m colors with c_i balls each, place each color as a contiguous arc to maximize the number of maximal runs where every color appears exactly once.

Level: Medium7 of 10
Topics: Math, Greedy, Sorting
Solved: No attempts yet

Problem

There are $n$ bowls arranged in a circle.

There are many balls of various colors. There are $m$ different colors, and there are $c\_i$ balls of the $i$ -th color.

Distribute all the balls into the bowls. For each color, choose a contiguous range of bowls of size $c\_i$ and put one ball of that color into each bowl in the range. A contiguous range is a set of consecutive bowls around the circle. Ranges of different colors may overlap.

A bowl is rainbow if it contains exactly one ball of each color. A rainbow bowl range is a contiguous run of rainbow bowls that cannot be extended by adding another rainbow bowl.

Arrange the balls to maximize the number of rainbow bowl ranges. Given $n$ and the number of balls of each color, find the maximum number of rainbow bowl ranges that can be formed.

Input

The first line contains two integers $n$ $(2 \le n \le 10^9)$ and $m$ $(1 \le m \le 10^5)$ . Each of the next $m$ lines contains a single integer $c\_i$ $(1 \le c\_i \le n)$ .

Output

Print a single integer, the maximum number of rainbow bowl ranges that can be formed.

Examples2

Example 1
Input
```
4 2
3
3
```
Expected output
```
2
```
Example 2
Input
```
10 11
3
1
4
1
5
9
2
6
5
3
5
```
Expected output
```
1
```