Олимпиадный тренинг

Задача . No Change


Задача

Темы: дп

Фермер Джон на рынке. У него в кармане K монет (1<=K<=16), каждая в диапазоне 1..100,000,000. ФД хочет сделать серию из N покупок (1 <= N <= 100,000), причём i-ая покупка имеет стоимость c(i) (1 <= c(i) <= 10,000). Во время выполнения последовательности покупок, ФД может периодически останавливаться и платить за все покупки выполненные с момента последней оплаты (конечно монета должна быть достаточно большой для этого). Покупки всегда делаются одной монетой, но у продавцов нет сдачи. Поэтому, если монета больше, чем количество денег, которое он должен заплатить, то разница теряется.
Определите максимальное количество денег, с которым ФД может закончить покупку всех N покупок в заданной последовательности. Выведите -1, если ФД не может сделать все покупки.
PROBLEM NAME: nochange
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..1+K: Каждая строка содержит количество денег на соответствующей монете ФД
* Строки 2+K..1+N+K: Эти N строк содержат стоимости покупок ФД


Формат выходных данных
* Строка 1: Максимальное количество денег, которое окажется у фермера в окнце покупок, или -1 если ФД не сможет выполнить все покупки.
Примечание
ФД потратит монету с ценностью 10 на первые две покупки, и затем монету с ценностью 15 на оставшиеся покупки. У него останется монета с ценностью12.


Примеры
№Входные данныеВыходные данные
1 
3 6
12
15
10
6
3
3
2
3
7
 
12
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет