В Сильвертауне расположены n розничных магазинов. В логистический центр города доставили m типов товаров с различным количеством, которые необходимо распределить по всем розничным магазинам. Логистическому центру необходимо распределить все товары по магазинам, следуя следующим правилам:
- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).
Пусть x - это максимальное количество товаров, предоставленных любому магазину. Для успешной реализации товаров необходимо обеспечить, чтобы x было как можно меньше. Другими словами необходимо свести к минимуму максимальное количество товаров, которые предоставляются любому магазину.
Напишите для логистического центра программу, которая бы находила минимально возможное x.
Входные данные
Первая строка входных данных содержит два натуральных числа, записанных через пробел:
n и
m (
1 <= m <= n <= 105) - количество розничных магазинов и количество типов товаров. Во второй строке содержится
m целых чисел
qi - количество
i-го типа товара (0
<= i < 105,
1 <= qi <= 105).
Выходные данные
Выведите минимально возможное
x.
Примечание
В первом тестовом примере оптимальным распределением будет следующее:
- 11 продуктов типа 0 распределяются по первым четырем магазинам в следующих количествах: 2, 3, 3, 3
- 6 продуктов типа 1 распределяются по двум другим магазинам в следующих количествах: 3, 3
Максимальное количество товаров, предоставляемых в любой магазин, составляет max(2, 3, 3, 3, 3, 3) = 3.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 2
11 6 |
3 |
| 2 |
7 3
15 10 10 |
5 |
| 3 |
1 1
100000 |
100000 |