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 atleast 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
anupam_akib:
20210526 22:31:19
Only backtracking works. No need memorization 

thanos_tapras:
20200607 21:14:17
Niceeeee! Dp with memoisation. 

khoaph:
20200521 04:04:49
No need to use dp, just recursion 

rising_stark:
20200430 12:11:15
The problem is good for beginners(for now) like me to get a good hold of bottomup dp. 

tarungupta:
20200322 07:12:22
Simple Recursion :) 

danos:
20191201 07:13:08
AC in ONE GO !!! 

sandeepd:
20191130 20:49:48
Good problem, weak test cases. 

smit_da191:
20190731 13:45:22
Accepted in one go!!! 

dmorgans:
20190529 13:09:29
AC in 1go.... 

dhruv2212000:
20190321 06:03:00
Standard DP problem. Here's the hint if barney is giving j gifts to i girls then number of ways he can arrive at this situation can be by giving [jlower(I th girl) , j  upper(I th girl) ] gifts from total gifts to (i1)th girl and so on :) 
Added by:  Ankit Kumar Vats 
Date:  20111021 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Inspired 