Задачі
Краватки
Краватки
На відкритті <<Турніру Чемпіонів>> перед учасниками і гостями збирається виступити N членів журі. Щоб показати єдність всіх представників журі, було прийнято рішення надіти їм краватки одного кольору. Все краватки зберігаються в скрині, яка знаходиться в темній кімнаті, та кожна з них має один з M кольорів. У кімнату можна увійти тільки один раз, вийняти зі скрині деяку кількість краваток і винести їх з кімнати. Потрібно визначити мінімальну кількість краваток, яку необхідно вийняти зі скрині, щоб серед них гарантовано було не менше N краваток одного кольору.
\InputFile
Програма зчитує зі стандартного пристрою уведення два рядки. Перший рядок містить два цілих числа N та M (1≤N≤10^6, 1≤M≤10^4). У другому рядку задано M чисел, кожне з яких означає кількість краваток відповідного кольору. Всі числа цілі невід’ємні та не перевищують 10^9.
\OutputFile
Програма повинна вивести на стандартний пристрій виведення одне число -- мінімальну кількість краваток, яку необхідно вийняти із скрині. Якщо гарантувати наявність N краваток одного кольору не можливо, необхідно вивести число −1.
Вхідні дані #1
3 3 4 5 6
Вихідні дані #1
7