Minimum Coin Change Problem

You are given a target amount (A) and a list of coin denominations. Your task is to determine the minimum number of coins required to form the exact amount (A) using the coins provided. Formally, given coin denominations (c_1, c_2, \dots, c_n) and a target amount (A), you need to find non-negative integers (x_1, x_2, \dots, x_n) such that (c_1x_1 + c_2x_2 + \dots + c_nx_n = A) and the sum (x_1 + x_2 + \dots + x_n) is minimized. If no combination of the coins can sum up to (A), output (-1).

Example:
For (A = 11) and coins ([1, 2, 5]), one optimal solution is (5 + 5 + 1 = 11) which uses 3 coins.

inputFormat

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

1. The first line contains a non-negative integer (A), the target amount.
   
2. The second line contains a positive integer (n), the number of coin denominations.
   
3. The third line contains (n) space-separated positive integers representing the coin denominations.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of coins required to form the amount (A). If it is impossible to form (A) with the given coin denominations, output (-1).## sample

11
3
1 2 5

3