Minimum Coins Problem

You are given an amount of money and a list of coin denominations. Your task is to determine the minimum number of coins required to sum up exactly to the given amount. If it is impossible to form the exact amount with the provided coins, you should output \( -1 \).

Note: Use dynamic programming to solve the problem. The recurrence relation is given by:

[ dp[i] = \min_{\text{for each coin } c \leq i} (dp[i-c] + 1)]

with the base case \( dp[0] = 0 \). If \( dp[amount] \) remains infinity (or a very large number) then the answer is \( -1 \).

inputFormat

The input is read from standard input (stdin) and consists of three lines:

• The first line contains an integer amount, which is the target amount of money.
• The second line contains an integer n, representing the number of coin denominations.
• The third line contains n space-separated integers, each representing a coin denomination.

outputFormat

Output a single integer on standard output (stdout) — the minimum number of coins needed to form the given amount. If it is not possible, output \( -1 \).

## sample

11
4
1 5 6 8

2

</p>