Perhaps you have read that some problems are so classic
that they barely need a statement.
For this one,
given a collection of *n* coins with different values
and a target amount *A*,
we ask you to indicate the way to add up to *A*
by using coins of the largest possible values.
In particular, a way is better than another one
if the former uses more coins of the largest value;
in the event of a tie, if it uses more coins of the second largest value, etc.

**Input**

Input consists of several cases.
Each case begins with the number of coins *n* between 1 and 100,
followed by *n* different integer numbers *v*_{1}, …, *v*_{n},
where 1≤ *v*_{i}≤ 10000.
Finally, we have an integer number 1≤ *A*≤ 100000.

**Output**

For every case, print in non-increasing order
the necessary coins to get *A*,
choosing the combination with coins of largest value in case of a tie.
If there is no solution, print −1.

Public test cases

**Input**

8 1 2 5 10 25 50 100 200 481 3 1 4 5 5 6 428 19 521 67 84 101 75 6 428 19 521 67 84 101 749

**Output**

200,200,50,25,5,1 5 -1 521,19,19,19,19,19,19,19,19,19,19,19,19

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++