Minimize the Jealousy Value in Marble Distribution

A marble factory has donated some marbles to a kindergarten. There are \(M\) different colors of marbles, and every marble has one unique color. The teacher needs to distribute all the marbles among \(N\) children. Each child who receives marbles must get marbles of exactly one color (a child may get no marbles at all).

When distributing the marbles, we define the jealousy value as the maximum number of marbles given to any child. The teacher wants to minimize this jealousy value. That is, the teacher wants to partition the marbles of each color into groups (each group given to one child) so that every child (if they receive marbles) gets at most \(x\) marbles, and all marbles are distributed.

Formally, for any chosen \(x\), for each color with \(c\) marbles, it must be partitioned into \(\lceil \frac{c}{x} \rceil\) groups (each group size is at most \(x\)). If the total number of groups summed over all colors does not exceed \(N\) (since each group goes to a different child), then it is possible to distribute all marbles with a jealousy value \(x\). Your task is to compute the minimum possible \(x\) such that this is feasible.

Example: Suppose there are 2 colors. There are 4 red marbles and 7 blue marbles, and \(N = 5\) children. For \(x = 3\): the red marbles can be partitioned into \(\lceil \frac{4}{3} \rceil = 2\) groups and the blue marbles into \(\lceil \frac{7}{3} \rceil = 3\) groups. In total, 2 + 3 = 5 groups are formed, so the jealousy value is 3 which is the minimum possible.

inputFormat

The input consists of two lines.

The first line contains two integers \(N\) and \(M\) where \(N\) (\(1 \leq N \leq 10^9\)) is the number of children, and \(M\) (\(1 \leq M \leq 10^5\)) is the number of different marble colors.

The second line contains \(M\) positive integers \(c_1, c_2, \dots, c_M\) (\(1 \leq c_i \leq 10^9\)), where \(c_i\) represents the number of marbles of the \(i\)th color.

outputFormat

Output a single integer, the minimum possible jealousy value \(x\) such that all marbles can be distributed under the given conditions.

sample

5 2
4 7

3