|
Сдача
(Время: 1 сек. Память: 16 Мб Сложность: 44%)
Когда Миша и Маша покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца – некоторое количество мелочи. Дело происходило утром, поэтому продавцу нужно было экономить мелочь, и он хотел отдать сдачу минимальным количеством монет. Подумав некоторое время, они точно определили, с каким количеством монет продавцу придется расстаться.
А вы сможете решить такую задачу?
Входные данные
В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10) – количество различных номиналов монет, содержащихся в кассе. Можно считать, что количество монет каждого номинала достаточно. На следующей строке содержится N целых чисел ai (0 < ai ≤ 2000) – номиналы монет. В третьей строке записано одно число K (1 ≤ K ≤ 106) – сумма, которую нужно набрать.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество монет, которое придется отдать продавцу, или -1, если продавец вообще не сможет дать им сдачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 5 7
19
| 3 |
| 2 | 5
7 8 9 10 11
13
| -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
