Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Сдача

(Время: 1 сек. Память: 16 Мб Сложность: 44%)

Когда Миша и Маша покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца – некоторое количество мелочи. Дело происходило утром, поэтому продавцу нужно было экономить мелочь, и он хотел отдать сдачу минимальным количеством монет. Подумав некоторое время, они точно определили, с каким количеством монет продавцу придется расстаться.

А вы сможете решить такую задачу?

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

В первой строке входного файла INPUT.TXT записано число N (1 <= N <= 10) – количество различных номиналов монет, содержащихся в кассе. Можно считать, что количество монет каждого номинала достаточно. На следующей строке содержится N целых чисел ai (0 < ai <= 2000) – номиналы монет. В третьей строке записано одно число K (1 <= K <= 106) – сумма, которую нужно набрать.

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

В выходной файл OUTPUT.TXT выведите минимальное количество монет, которое придется отдать продавцу, или -1, если продавец вообще не сможет дать им сдачу.

Примеры

INPUT.TXTOUTPUT.TXT
13
1 5 7
19
3
25
7 8 9 10 11
13
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483