Sample Problem

Taken from CIS Infinity Blog

Sample Problem

Description:

You are given a limited number of coins of various denominations, and a certain amount. You are to compute how many ways there are to pick the coins to add up to that amount. For example, given 12 coins of 1-cent value, 2 coins of 5-cent value and 3 coins of 10-cent value, and an amount of 15 cents, there are 4 combinations:

• 2 5-cents coins and 5 1-cent coins
• 1 5-cents coins and 10 1-cent coins
• 1 10-cent coins and 1 5-cent coin
• 1 10-cent coins and 5 1-cents coins
  

The answer therefore should be 4.

Input:

The first line of the input file consists of a single positive integer indicating the number of different coin denominations. The next line of the input file consists of a single positive integer representing the total amount. The remaining lines of the input file each consist of a pair of positive integer representing a coin denomination followed by the number of coins of that denomination available. All numbers are in the range of [1, 100].

The sample input and output are shown below.

Sample input:

3

15

1 12

5 2

10 3

Sample Output:

4