Задача Галстуки (CRAVAT)
На открытии «Турнира Чемпионов» перед участниками и гостями собирается выступить N членов жюри. Чтобы показать единство всех представителей жюри, было принято решение надеть галстуки одного цвета. Все галстуки хранятся в сундуке, который находится в темной комнате, и каждый из них имеет один из M цветов. В комнату можно войти только один раз, вытащить из сундука некоторое количество галстуков и вынести их из комнаты. Требуется определить минимальное количество галстуков, которое необходимо вытащить из сундука, чтобы среди них гарантировано было не менее N галстуков одного и того же цвета.
Формат ввода/вывода:
Программа считывает из стандартного устройства ввода две строки. Первая строка содержит два целых числа N и M (1≤N≤106, 1≤M≤104). Во второй строке заданы M чисел, каждое из которых обозначает количество галстуков соответствующего цвета. Все числа целые неотрицательные и не превосходят 109.
Программа должна вывести на стандартное устройство вывода одно число – минимальное количество галстуков, которое потребуется вытащить из сундука. Если гарантировать наличие N галстуков одного цвета невозможно, необходимо вывести число −1.
Пример:
|
Ввод |
вывод |
|
3 3 4 5 6 |
7 |