Coin change problem
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\}.
Input data
First line contains two space-separated integers: number of units n~(1 \le n \le 250) and number of coin types m~(1 \le m \le 50). The second line contains m integers c_i~(1 \le c_i \le 50) describing the respective values of each coin type. Each c_i is guaranteed to be distinct.
Output data
Print the number of ways to make change.
Examples
4 3 1 2 3
4
10 4 2 5 3 6
5