Задача Галстуки (CRAVAT)

На открытии «Турнира Чемпионов» перед участниками и гостями собирается выступить N членов жюри. Чтобы показать единство всех представителей жюри, было принято решение надеть галстуки одного цвета. Все галстуки хранятся в сундуке, который находится в темной комнате, и каждый из них имеет один из M цветов. В комнату можно войти только один раз, вытащить из сундука некоторое количество галстуков и вынести их из комнаты. Требуется определить минимальное количество галстуков, которое необходимо вытащить из сундука, чтобы среди них гарантировано было не менее N галстуков одного и того же цвета.

Формат ввода/вывода:

Программа считывает из стандартного устройства ввода две строки. Первая строка содержит два целых числа N и M (1≤N≤10⁶, 1≤M≤10⁴). Во второй строке заданы M чисел, каждое из которых обозначает количество галстуков соответствующего цвета. Все числа целые неотрицательные и не превосходят 10⁹.

Программа должна вывести на стандартное устройство вывода одно число – минимальное количество галстуков, которое потребуется вытащить из сундука. Если гарантировать наличие N галстуков одного цвета невозможно, необходимо вывести число −1.

Пример: