Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P
1, P
2, ..., P
N рублей. У продавца есть M банкнот номиналом Q
1, Q
2, ..., Q
M. рублей. Определите, смогут ли они рассчитаться.
Входные данные
Программа получает на вход сумму S. Далее идет число N затем P
1, P
2, ..., P
N. Далее идет число M, затем Q
1, Q
2, ..., Q
M.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.
Выходные данные
Если продавец сможет рассчитаться с покупателем, выведите наименьшее количество банкнот, которое придется отдать продавцу на сдачу.
Если они не могут рассчитаться, выведите число -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
4
3 3 9 3
2
6 2
|
1
|
|
2
|
100
3
74 35 8
2
19 6
|
-1
|