e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

БАНКОМАТ

БАНКОМАТ

У банкоматі є банкноти N різних номіналів a1, a2, …, aN. Клієнт хоче отримати суму в К грн. Необхідно визначити, за допомогою якої мінімальної кількості купюр можна видати цю суму і якими саме купюрами. Вважається, що у банкоматі необмежена кількість купюр кожного номіналу.

Вхідні дані:

Перший рядок - число N - кількість номіналів

Другий рядок - номінали - цілі числа a1, a2, …, aN, розділені пробілами

Третій рядок - сума К, яку клієнт хоче отримати

Всі числа цілі і знаходяться у діапазоні від 1 до 100000.

Вихідні дані:

Перший рядок - кількість купюр, які видасть банкомат

Другий рядок - пари чисел (номінал та відповідна кількість купюр цього номіналу), розділених пробілами.

Якщо існує декілька варіантів видачі, то виведіть будь-який з них.

Якщо задану суму К не можна видати, то виведіть одне число -1

Пояснення до тесту з умови:

Банкомат видасть 3 купюри:

1 купюра номіналом 500 грн.

2 купюри номіналом 100 грн.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
2
100 500 
700
Выходные данные #1
3
500 1 100 2
Входные данные #2
2
100 500 
250
Выходные данные #2
-1