Автомат с монетами: когда жадность ошибается

В школьном буфете поставили автомат, который выдаёт сдачу монетами. Он работает «жадно»: всегда берёт самую крупную монету, которая не превышает оставшуюся сумму, и повторяет.

Иногда такой алгоритм даёт лишние монеты (хотя можно было разменять той же суммой меньшим числом монет).

Найди самую маленькую сумму x (в пределах от 0 до A), для которой жадный алгоритм выдаёт строго больше монет, чем оптимальный размен. Если такой суммы нет, выведи -1.

Важно: номиналы могут быть очень большими (как 64-битные целые на олимпиадах), но сумма A ограничена.

Формат ввода

В первой строке даны два целых числа n и A — количество номиналов и максимальная проверяемая сумма. Во второй строке даны n различных целых чисел c1, c2, ..., cn — номиналы монет.

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

Выведи одно целое число — минимальную сумму x (0 ≤ x ≤ A), где жадный размен хуже оптимального, или -1, если жадный алгоритм оптимален для всех сумм от 0 до A.

Ограничения

• 1 ≤ n ≤ 20
• 0 ≤ A ≤ 1 000 000
• 1 = c1 < c2 < ... < cn
• 1 ≤ ci ≤ 10^12 (возможны значения больше 2^31)

Пример

Ввод:

4 28
1 2 5 10

Вывод:

-1

(Для всех сумм до 28 жадный размен даёт минимальное число монет.)

Ключевое наблюдение: если жадный алгоритм хоть где-то ошибается, то существует контрпример среди сумм меньше c[n-1] + c[n] (две самые большие монеты). Значит, не нужно проверять все огромные суммы и тем более зависеть от величин ci (они могут быть до 1e12) — достаточно ограничиться limit = min(A, c[n] + c[n-1] - 1).

Дальше делаем два независимых подсчёта для всех x от 1 до limit:

• Оптимум: динамика по сумме (unbounded knapsack). dp[s] — минимальное число монет, чтобы набрать сумму s.
• Жадный: симуляция выбора монет от больших к меньшим.

План:

• Отсортируй номиналы по возрастанию, вычисли limit.
• Посчитай dp[0..limit]: dp[0]=0, остальные = INF.
• Для каждой монеты c (если c > limit, дальше можно не брать):
• для s от c до limit: обнови dp[s] = min(dp[s], dp[s-c] + 1).
• Для каждого x от 1 до limit посчитай greedy(x) (монеты в обратном порядке). Один шаг жадного:
• k = x // c; cnt += k; x -= k * c
• Первое x, где greedy(x) > dp[x], и есть ответ. Если не нашлось — -1.

Сложность: O(n * limit) по времени и O(limit) по памяти, при n <= 20 и limit <= 1e6 это проходит.

Частая ошибка: строить DP до A, забывая про ограничение c[n-1] + c[n], или пытаться учитывать монеты > limit (они не могут участвовать в суммах до limit).