Jewelry Box

Time limit1sMemory limit128 MB

Summary

Given N children and piles of jewels per color, find the minimum possible maximum pile size when each color's jewels are split among some children.

Level: Medium5 of 10
Topics: Binary search, Greedy
Solved: No attempts yet

Problem

A jewelry factory donated a box of jewels to a kindergarten. Each jewel has one of M different colors. The principal wants to distribute every jewel in the box among N children. Some children may receive no jewels, but every child who receives jewels must receive jewels of only one color.

If one child receives too many jewels, the other children may become jealous. The jealousy value is defined as the number of jewels held by the child who receives the most jewels. The principal wants to distribute the jewels so that this value is as small as possible.

For instance, suppose there are 4 red jewels (RRRR), 7 blue jewels (BBBBBBB), and 5 children. The jewels can be distributed as RR, RR, BB, BB, BBB. Then the largest number received by any child is 3, so the jealousy value is 3, and it is impossible to make it smaller.

Given the number of jewels of each color and the number of children, write a program that finds the minimum possible jealousy value.

Input

The first line contains the number of children N and the number of colors M. (1 <= N <= 10^9, 1 <= M <= 300,000, M <= N)

Each of the next M lines contains one integer: the number of jewels of one color. The value on the K-th of these lines is the number of jewels of color K, and every value is an integer between 1 and 10^9, inclusive.

Output

Print the minimum possible jealousy value on the first line.

Examples2

Example 1
Input
```
5 2
7
4
```
Expected output
```
3
```
Example 2
Input
```
7 5
7
1
7
4
4
```
Expected output
```
4
```