БАНКОМАТ
В банкомате имеются банкноты N различных номиналов: a[1], a[2], …, a[N]. Клиент желает снять сумму в размере К рублей. Ваша задача — определить минимальное количество купюр, необходимое для выдачи этой суммы, и указать, какими именно купюрами она будет выдана. Предполагается, что банкомат располагает неограниченным количеством купюр каждого номинала.
Входные данные
Первая строка содержит число N — количество различных номиналов.
Вторая строка содержит номиналы — целые числа a[1], a[2], …, a[N], разделенные пробелами.
Третья строка содержит сумму К, которую клиент хочет получить.
Все числа являются целыми и находятся в диапазоне от 1 до 100000.
Выходные данные
Первая строка должна содержать количество купюр, которые банкомат выдаст.
Вторая строка должна содержать пары чисел (номинал и количество купюр этого номинала), разделенные пробелами.
Если существует несколько способов выдачи суммы, вы можете вывести любой из них.
Если невозможно выдать заданную сумму К, выведите число -1.
Пояснение к тесту из условия:
Банкомат выдаст 3 купюры:
1 купюра номиналом 500 рублей.
2 купюры номиналом 100 рублей.