Minimum Coins Problem

You are given an integer amount and a list of coin denominations. Your task is to determine the minimum number of coins required to make up the given amount. If it is not possible to obtain the amount with any combination of the given coins, output -1.

The solution should utilize a dynamic programming approach where you compute the minimum number of coins needed for each sub-amount from 0 to amount.

Note: The answer must be computed using an algorithm that reads input from stdin and writes output to stdout.

inputFormat

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

Line 1: An integer representing the amount. Line 2: An integer n representing the number of coin denominations. Line 3: n space-separated integers, each representing a coin denomination. (If n is 0, this line will be empty.)

outputFormat

Output a single integer to standard output (stdout) which is the minimum number of coins required to form the given amount. If it is not possible to form that amount, output -1.## sample

11
3
1 2 5

3