Сомы для базара


Отправить решение Решать в редакторе

Сложность: 34%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Сомы для базара

В кошельке Нурлана неограниченно много монет k номиналов c₁, …, cₖ сомов. Какое наименьшее количество монет нужно, чтобы расплатиться ровно на S сомов? Если это невозможно — выведите -1.

Формат ввода

В первой строке записаны k и S (1 ≤ k ≤ 8, 0 ≤ S ≤ 10⁵). Во второй строке — k различных натуральных номиналов cᵢ ≤ 100.

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

Выведите наименьшее число монет либо -1. При S = 0 ответ равен 0.

Пример 1

Вход:

3 11
1 2 5

Выход:

3

Пример 2

Вход:

1 3
2

Выход:

-1

Комментарии

Еще нет ни одного комментария.