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

Вхідні дані:

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

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

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

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

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

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

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

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

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

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

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

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

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