favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic programming

Coin change problem

You are working at the cash counter at a fun-fair, and you have different types of coins available to you in infinite quantities. The value of each coin is already given. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

For example, if you have 4 types of coins, and the value of each type is given as 8, 3, 1, 2 respectively, you can make change for 3 units in three ways: {1, 1, 1}, {1, 2}, and {3}.


First line contains two space-separated integers: number of units n (1n250) and number of coin types m (1m50). The second line contains m space-separated integers ci (1ci50) describing the respective values of each coin type. Each ci is guaranteed to be distinct.


Print the number of ways to make change.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 3
1 2 3
Output example #1
Input example #2
10 4
2 5 3 6
Output example #2