ЗАДАЧА J

Сказочные монеты

Имя входного файла:money.in
Имя выходного файла:money.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

Однажды наш «сказочный герой», отправляясь в путешествие за границу, решил взять с собой такое количество «сказочных монет», чтобы ими можно было дать таможеннику взятку на любую сумму в диапазоне от 1 до некоторого числа X. Всего есть несколько типов монет и у каждого типа монет своя стоимость. Понятное дело, что герой хочет добиться того, чтобы общее количество монет, которые он возьмёт с собой, было минимальным. Напишите программу, которая определит, можно ли вообще собрать набор монет, удовлетворяющий условию. И, если можно, то определите, какое минимальное количество «сказочных монет» должно быть в таком наборе.

Входные данные

В первой строке входного файла записано число X (1<=X<=1000).
Во второй строке записаны несколько чисел (не более, чем 50) - стоимости каждого типа монет.

Выходные данные

Если собрать набор монет, удовлетворяющих условию не удастся, то в выходной файл выведите -1. Иначе в выходной файл выведите единственное число -- минимальное количество сказочных монет, которое должно быть в таком наборе.

Пример


money.in money.out
1000
1
1000
1000
1 2
501