ATM
In the ATM, there are banknotes available in N different denominations: a[1], a[2], …, a[N]. A customer wishes to withdraw a total of K UAH. Your task is to determine the minimum number of banknotes required to dispense this amount and identify which banknotes to use. Assume the ATM has an unlimited supply of each denomination.
Input
The first line contains the integer N, representing the number of different denominations.
The second line lists the denominations as integers
a[1],a[2], …,a[N], separated by spaces.The third line contains the integer K, the amount the customer wants to withdraw.
All numbers are integers and fall within the range of 1 to 100000.
Output
The first line should display the total number of banknotes the ATM will dispense.
The second line should list pairs of numbers, each consisting of a denomination and the corresponding number of banknotes of that denomination, separated by spaces.
If there are multiple ways to dispense the amount, any valid solution is acceptable.
If it is impossible to dispense the specified amount K, output a single number -1.
Example Explanation:
For the given test case, the ATM will dispense 3 banknotes:
1 banknote of 500 UAH denomination.
2 banknotes of 100 UAH denomination.