Minimum Coin Change

You are given an integer amount and a list of coin denominations. Your task is to select a set of coins such that their sum equals amount using a greedy approach. In each step, you choose the largest coin denomination possible that does not exceed the remaining amount.

If it is impossible to form the exact amount, output -1. Otherwise, output the selected coins in the order they are chosen. Mathematically, if the chosen coins are \(c_1, c_2, \dots, c_k\), then they must satisfy \[ \sum_{i=1}^{k} c_i = \text{amount} \] and the number of coins should be as small as possible under the greedy selection strategy.

Note: The greedy algorithm works correctly for many canonical coin systems. For non-canonical systems, it may not always yield a minimum count; however, for the purpose of this problem, assume that the input denominations will work correctly with the greedy approach.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer amount representing the target amount.
• The second line contains an integer n denoting the number of available coin denominations.
• The third line contains n space-separated integers representing the coin denominations.

outputFormat

Output a single line to standard output (stdout). If it is possible to form the exact amount using the coins, print the selected coin values separated by a single space. If it is not possible to form the amount, output -1.

11
3
1 2 5

5 5 1