Knapsack - Рюкзак
In some country in circulation there are notes of certain denominations. National Bank wants the cash machine to give out any requested amount with a minimum number of banknotes, considering that the amount of banknotes of each denomination is unlimited.
Help the National Bank to solve this problem.
First line contains the number of banknotes denominations in circulation n (n ≤ 100). Second line contains n different positive integers
xn not greater than
106 - the banknotes denominations. Third line contains the sum s (s ≤
106) that you want to give.
Print in the first line the minimal number of summands (or -1 if such representation does not exist). In the second line print these summands in any order.
5 1 3 7 12 32 40
3 32 7 1