# 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**}.

#### Input

First line contains two space-separated integers: number of units **n** (**1** ≤ **n** ≤ **250**) and number of coin types **m** (**1** ≤ **m** ≤ **50**). The second line contains **m** space-separated integers `c`

(_{i}**1** ≤ `c`

≤ _{i}**50**) describing the respective values of each coin type. Each `c`

is guaranteed to be distinct._{i}

#### Output

Print the number of ways to make change.

4 3 1 2 3

4

10 4 2 5 3 6

5