Seating Arrangement

Olympiad preparation has many tasks for the jury and organizing committee, such as writing statements, preparing tests, writing solutions, and setting up computers. It is easy to forget to seat the participants in the rooms correctly. This time, the committee wants to use the seats efficiently and plans a compact seating of the schoolchildren into $M$ available rooms. A seating is called compact if, for any two different rooms, the numbers of children in them differ by at most one. A member of the jury with extrasensory abilities predicted that students from $K$ schools will reach the on-site round. He also predicted that exactly $n_i$ students will come from the $i$-th school ($1 \le i \le K$). Many committee members are skeptical of such predictions, but they have a habit of coming true. Assuming the predictions are correct, find the maximum possible number of participants who can be in one room under a compact seating.

The first line contains two integers $M$ and $K$, the number of rooms and the number of schools ($1 \le M \le 10^9$, $1 \le K \le 100000$). The second line contains $K$ integers $n_1, n_2, \ldots, n_K$ separated by spaces ($1 \le n_i \le 10^9$).

Print one integer, the maximum number of people in one room under a compact seating.

In the first test, there is only one compact seating: each of the two rooms gets 7 people.