ЗАДАЧА J
Сказочные монеты
| Имя входного файла: | money.in |
| Имя выходного файла: | money.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Однажды наш «сказочный герой», отправляясь в путешествие за границу, решил взять с собой такое количество «сказочных монет», чтобы ими можно было дать таможеннику взятку на любую сумму в диапазоне от 1 до некоторого числа X. Всего есть несколько типов монет и у каждого типа монет своя стоимость. Понятное дело, что герой хочет добиться того, чтобы общее количество монет, которые он возьмёт с собой, было минимальным. Напишите программу, которая определит, можно ли вообще собрать набор монет, удовлетворяющий условию. И, если можно, то определите, какое минимальное количество «сказочных монет» должно быть в таком наборе.
Входные данные
В первой строке входного файла записано число X (1<=X<=1000).Во второй строке записаны несколько чисел (не более, чем 50) - стоимости каждого типа монет.
Выходные данные
Если собрать набор монет, удовлетворяющих условию не удастся, то в выходной файл выведите -1. Иначе в выходной файл выведите единственное число -- минимальное количество сказочных монет, которое должно быть в таком наборе.Пример
| money.in | money.out |
|---|---|
|
|
|
|