Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
В связи с обвалом рубля работники кондитерской фабрики стали получать зарплату продукцией — новогодними подарками. Фабрика производит N видов подарков, i-й из которых стоит Pi рублей. Можно считать, что на складе найдётся любое необходимое количество подарков любого вида.
Зарплата Ивана Петровича составляет S рублей. Сотрудники бухгалтерии уже устали раздавать коробки с конфетами, поэтому они хотят выдать Ивану Петровичу как можно меньше подарков. Разумеется, суммарная стоимость всех выданных подарков должна быть в точности равной S.
Помогите бухгалтерии определить минимальное количество подарков, которое нужно выдать Ивану Петровичу.
Входные данные
Первая строка содержит целые числа S и N (0 <= S <= 10^4, 0 <= N <= 100) — соответственно величину зарплаты Ивана Петровича и количество видов подарков.
Вторая строка содержит N целых чисел Pi (1 <= Pi <= 10^4) — стоимости каждого вида подарков.
Выходные данные
Выведите одно целое число — минимально возможное количество подарков, общая стоимость которых равна S. Если требуемую стоимость получить невозможно, выведите -1.
Примеры
| Входные данные | Выходные данные |
1000 3
320 700 100 | 4 |
6000 4
3500 500 1150 1275 | 5 |
1200 3
110 280 630 | -1 |
Для отправки решений необходимо выполнить вход.
|