Алла хочет купить дом на Алгосах. Для этого ей надо много наличных, которые она собирается получить в банкомате. Банкомат приличный, поэтому в нём есть бесконечно много банкнот каждого номинала. Всего номиналов k штук. Дом мечты Аллы стоит x франков.
Найдите минимальное количество банкнот, которые в сумме дадут x франков. Если в набор входит несколько банкнот одинакового номинала, то учитывать надо их все.
Например, если необходимо набрать 15 франков, а в банкомате купюры по 5 франков, то минимальное число купюр —- 3.
В первой строке дана сумма, которую хочет получить Алла –— натуральное число x (1 ≤ x ≤ 104).
Во второй строке дано число различных номиналов k.
В третьей строке даны k чисел (1 ≤ k ≤ 1000) —– номиналы купюр. Все номиналы лежат в диапазоне от 1 до 104. Номиналы купюр могут повторяться.
Выведите единственное число —– минимальное количество купюр, которыми можно набрать x франков. Если нельзя набрать в точности x франков, то выведите -1.
|
130 4 10 3 40 1 |
4 |
|
100 2 7 5 |
16 |
|
1 1 1 |
1 |