Cow Cash

Interview

Time limit1sMemory limit128 MB

Summary

Count the number of unordered ways to make an amount N using V coin denominations, where each coin can be used any number of times.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Array
Solved: No attempts yet

Problem

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).

Input

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

Output

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

Examples5

Example 1
Input
```
3 10
1
2
5
```
Expected output
```
10
```
Example 2
Input
```
1 1
1
```
Expected output
```
1
```
Example 3
Input
```
1 5
5
```
Expected output
```
1
```
Example 4
Input
```
1 7
2
```
Expected output
```
0
```
Example 5
Input
```
2 6
2
3
```
Expected output
```
2
```