Coin Change Problem

Given a target amount \(N\) and a list of coin denominations, determine the minimum number of coins required to form exactly \(N\). The coins can be used an unlimited number of times. If it is not possible to form the amount, output \(-1\). For instance, when \(N = 11\) and the coin set is \([1, 2, 5]\), the answer is 3. When \(N = 3\) and the coin set is \([2]\), it is impossible, so output \(-1\). Note that if \(N = 0\), then no coins are required.

inputFormat

The input is given via standard input (stdin) in the following format:

1. The first line contains a single integer representing the target amount \(N\).
2. The second line contains a single integer \(k\), the number of coin denominations.
3. The third line contains \(k\) space-separated integers representing the coin denominations.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of coins needed to achieve exactly the amount \(N\). If it is not possible, output \(-1\).

11
3
1 2 5

3