P7585 [COCI 2012/2013 #1] LJUBOMORA

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.

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 one line with one integer, representing the minimum jealousy value.

#### 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](https://hsin.hr/coci/archive/2012_2013/) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)** ___T4 LJUBOMORA___. Translated by ChatGPT 5