eolymp
bolt
Try our new interface for solving problems
Problems

БАНКОМАТ

БАНКОМАТ

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

Другий рядок - номінали - цілі числа a[1], a[2], …, a[N], розділені пробілами

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

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

Output data

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

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

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

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

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

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

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

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

Examples

Input example #1
2
100 500 
700
Output example #1
3
500 1 100 2
Input example #2
2
100 500 
250
Output example #2
-1