| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 262 | 159 | 144 | 59.504% |
Олимпиада всегда приносит много хлопот для жюри и оргкомитета, и очный тур Открытой олимпиады не является исключением из этого правила. Пока пишутся условия, готовятся тесты, создаются разборы и настраиваются компьютеры, очень легко забыть правильно рассадить участников олимпиады по аудиториям.
В этот раз, в целях рационального использования рабочих мест, оргкомитет олимпиады поставил перед собой задачу — создать компактную рассадку школьников по M имеющимся аудиториям. Рассадка называется компактной, если для любых двух различных аудиторий количества детей в них отличаются не более чем на один.
В жюри олимпиады имеется человек с экстрасенсорными способностями, который может очень точно предсказывать результаты будущих соревнований по программированию. Хотя результаты заочного тура ещё не известны, он без труда определил, что на очный тур пройдут ученики из K школ. Кроме того, было предсказано, что из i-й школы (1 ⩽ i ⩽ K) пройдёт в точности ni учеников. Хотя отношение большей части оргкомитета к подобным прогнозам зачастую скептическое, они имеют странное свойство сбываться, поэтому вам предлагается на всякий случай вычислить максимально возможное количество участников, которые попадут в одну аудиторию при компактной рассадке, если предсказание окажется верным.
В первой строке ввода находятся два целых числа M и K — количество аудиторий и количество школ, участвующих в очном туре олимпиады согласно предсказанию (1 ⩽ M ⩽ 109, 1 ⩽ K ⩽ 100 000).
В следующей строке находятся K чисел ni, разделённых пробелами, i-е из которых обозначает, сколько участников предположительно приедет из i-й школы (1 ⩽ ni ⩽ 109).
Выведите одно число — максимальное количество людей в аудитории при компактной рассадке.
2 2 5 9
7
1 2 20 10
30
В первом тесте существует только одна компактная рассадка — в каждую из аудиторий рассадить по 7 человек.