Description

A marble factory donated some marbles to a kindergarten. There are $M$ different colors of marbles, and each marble has exactly one color. The teacher needs to distribute all the marbles to $N$ children. All marbles given to the same child must be of the same color, and some children may receive no marbles at all.

We define the jealousy value as the maximum number of marbles given to any single child. Please help the teacher distribute the marbles so that the jealousy value is as small as possible.

For example, if there are $4$ red marbles ($\texttt{RRRR}$) and $7$ blue marbles ($\texttt{BBBBBBB}$), to be distributed among $5$ children, we can distribute them as: $\texttt{RR}$, $\texttt{RR}$, $\texttt{BB}$, $\texttt{BB}$, $\texttt{BBB}$. The jealousy value is then $3$, and this is the minimum possible.

Input Format

The input has $M+1$ lines.

The first line contains two positive integers $N, M$, representing the number of children and the total number of colors of marbles.

In the next $M$ lines, the $i$-th line contains a positive integer $x$ ($x \in [1,10^9]$), meaning there are $x$ marbles of color $i$.

Output Format

Output one line with one integer, representing the minimum jealousy value.

5 2
7
4

3

7 5
7
1
7
4
4

4

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le M \le 3 \times 10^5$, $1 \le N \le 10^9$, and $M \le N$.

Notes

The score of this problem follows the original COCI settings, with a full score of $120$.

Translated from COCI2012-2013 CONTEST #1 T4 LJUBOMORA.

Translated by ChatGPT 5