Cow Cash

The cows have not only formed their own government, they have also decided to create their own money system. In their rebellious way, they are curious about the values of coins. Traditionally, coins come in values such as 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2-unit coin added for good measure.

The cows want to know how many different ways a given amount of money can be assembled using a particular coin system. Each coin value may be used any number of times, and two ways that use the same coins in a different order are considered the same. For example, using the value set ${1, 2, 5, 10, \dots}$, the amount 18 can be made in many ways, including $18 \times 1$, $9 \times 2$, $8 \times 2 + 2 \times 1$, and $3 \times 5 + 2 + 1$.

Write a program that computes the number of ways to construct a given amount of money $N$ using $V$ coin values, where $1 \le N \le 10000$ and $1 \le V \le 25$. The answer is guaranteed to fit in a signed 64-bit integer (long long in C/C++, long in Java).

• Line 1: Two space-separated integers, $V$ and $N$
• Lines 2 to $V+1$: Each line contains one available coin value

• Line 1: A single line containing the total number of ways to construct $N$ money units using the $V$ coin values