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