Silvertown has n retail stores. The City Logistics Center delivered m types of goods with different quantities to be distributed to all retail stores. The Logistics Center needs to distribute all goods to the stores , following the following rules:
- Each store is allocated no more than one type of product, but any quantity.
- After distribution, each store is given a certain amount of goods (possibly zero).
Let x be the maximum number of items provided to any store. For successful sale of goods, it is necessary to ensure that x is as small as possible. In other words, it is necessary to reduce to a minimum the maximum number of products that are provided to any store.
Write a program for the logistics center that would find the smallest possible x.
Input
The first line of the input contains two space-separated natural numbers:
n and
m (
1 <= m <= n <= 10< sup>5) - the number of retail stores and the number of product types. The second line contains
m integers
qi - the quantity of the
i-th product type (0
;<= i < 105,
1 <= qi <= 105).
Imprint
Output the smallest possible
x.
Note
In the first test case, the optimal distribution would be:
- 11 products of type 0 are distributed to the first four stores in the following quantities: 2, 3, 3, 3
- 6 products of type 1 are distributed to two other stores in the following quantities: 3, 3
The maximum number of items provided to any store is max(2, 3, 3, 3, 3, 3) = 3.
Examples
| # |
Input |
Output |
| 1 |
6 2
116 |
3 |
| 2 |
7 3
15 10 10
| 5 |
| 3 |
1 1
100000 |
100000 |