BEHAPPY - Be Awesome As Barney Stinson


Barney Stinson ;) is way too flirty. He has many girlfriends and he wants to keep all of them happy. He has M girlfriends. He bought N gifts for them. Now he knows that some girlfriends need more gifts and some need less. So he decided that he will give at least Ai gifts and at most Bi gifts to his ith girlfriend. He has to give away all the N gifts. Tell us in how many different ways he can do this.

INPUT

For each test case, first line contains two integers M and N, then follows M lines each having two integers Ai and Bi (1 <= i <= M). Input ends with M and N both equal to 0 and that case should not be processed.

OUTPUT:

For each test case, output the number of different ways in which he can distribute those gifts in a single line.

Constraints

1 <= M <= 20, 1 <= N <= 100, 0 <= Ai, Bi <=100

Example

Input:

3 5
0 1
1 3
1 4
0 0

Output:

6

Explanation

He can distribute 5 gifts in his 3 girlfriends in 6 different ways as follows (0 1 4), (0 2 3), (0 3 2), (1 1 3), (1 2 2), (1 3 1).


hide comments
jyoti369: 2021-09-09 12:40:15

AC in one go. Beat my java soln which passed in 0.08 sec.

anupam_akib: 2021-05-26 22:31:19

Only backtracking works. No need memorization

thanos_tapras: 2020-06-07 21:14:17

Niceeeee! Dp with memoisation.

khoaph: 2020-05-21 04:04:49

No need to use dp, just recursion

rising_stark: 2020-04-30 12:11:15

The problem is good for beginners(for now) like me to get a good hold of bottom-up dp.

tarungupta: 2020-03-22 07:12:22

Simple Recursion :)

danos: 2019-12-01 07:13:08

AC in ONE GO !!!

sandeepd: 2019-11-30 20:49:48

Good problem, weak test cases.

smit_da191: 2019-07-31 13:45:22

Accepted in one go!!!

dmorgans: 2019-05-29 13:09:29

AC in 1go....


Added by:Ankit Kumar Vats
Date:2011-10-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Inspired