We are given an array of distinct positive integers $\{$a$1=1,$ a$2,...,$ an$\}$

that denote the denominations of coins in circulation. We are also

given a positive integer x$.$ Find the smallest number of coins such

that their sum equals x $($we let a$1=1$ so that this is always possible$).$

For example, in US the denominations of commonly used coins

are $($in cents$)\{1,5,10,25\}.$ If x $=51,$ then the smallest number of

coins that are needed is $3($two $25$ and one $1).$

Note that a greedy algorithm, which always selects the largest

denomination possible is not optimal in general. For example, if the

denominations are $\{1,7,10\}$ and x $=14.$ Then the greedy algorithm

will select one coin with denomination $10,$ then four coins with de$-$

nomination $1.$ In total, it requires $1+4=5$ coins. But we know we

can just select two coins of $7,$ which is optimal.

Write a program to solve this problem. Given $\{$a$1=1,$ a$2,...,$ an$\}$

and x$,$ the output of the program should include: