Coin change problem#9614
You are working as a cashier at a cheerful fair, and you have coins of different denominations. An unlimited number of coins is available for each denomination, and the value of each denomination is known. Determine the number of ways to pay a given amount using the available coin denominations.
For example, if you have coin denominations with values , and , the amount can be paid in the following ways: \{1, 1, 1\}, \{1, 2\} and .
The first line contains two integers: the amount n~(1 \le n \le 250) and the number of coin denominations m~(1 \le m \le 50). The second line contains integers c_i~(1 \le c_i \le 50), representing the values of the coin denominations. All c_i values are distinct.
Print the number of ways to pay the amount .
Example 1
Example 2