Купоны на скидку: минимум купонов

В школьном буфете есть несколько видов купонов-скидок. Каждый купон даёт скидку ровно на c рублей, и купонов каждого вида можно взять сколько угодно.

Кассир хочет собрать скидку ровно на S рублей, чтобы не возиться с мелочью. Ему важно использовать как можно меньше купонов.

Если собрать ровно S рублей невозможно, это тоже нужно честно сообщить.

Формат ввода

В первой строке записаны два целых числа S и m — нужная сумма скидки и количество видов купонов. Во второй строке записаны m целых чисел c1, c2, ..., cm — номиналы купонов.

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

Выведите одно целое число — минимальное количество купонов, чтобы получить скидку ровно S. Если это невозможно, выведите -1.

Ограничения

• 0 ≤ S ≤ 10000
• 1 ≤ m ≤ 50
• 1 ≤ ci ≤ 10000
• Купоны каждого вида можно использовать неограниченно много раз.

Пример

Ввод:

11 3
1 5 7

Вывод:

3

Пояснение: можно взять 5 + 5 + 1.

Ключевое наблюдение: если мы хотим набрать ровно x рублей скидки, то последний взятый купон мог быть любого номинала c. Тогда до него мы должны были набрать x-c, а ответ для x — это минимум среди вариантов dp[x-c] + 1.

Это работает, потому что купоны можно брать сколько угодно раз, и для каждой суммы важен только лучший (минимальный) способ набора меньших сумм — классическое «оптимальное подрешение».

План:

• Заведи массив dp[0..S], где dp[x] — минимум купонов для суммы x.
• Инициализация: dp[0] = 0, остальные как «невозможно» (например, большое число INF).
• Для всех x от 1 до S:
• перебери все номиналы c;
• если x - c >= 0 и dp[x-c] не INF, попробуй улучшить: dp[x] = min(dp[x], dp[x-c] + 1).
• Ответ: если dp[S] INF, выводи -1, иначе dp[S].

Сложность по времени: O(S * m), по памяти: O(S). При S ≤ 10000 и m ≤ 50 проходит легко.

Частая ошибка: перепутать задачу с «каждый купон можно взять один раз» и делать обновления в неправильном порядке. Здесь купоны неограниченные, но при формуле через «последний купон» порядок x=1..S безопасен и простой.