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
shahzada:
20170306 04:56:51
Should be moved to tutorial. 

kshubham02:
20170222 06:36:06
1. I realized after submitting that I am not even taking multiple test cases. Just inputting M and N once, no breaking at 0 0 or any of that shit.


.::Austin::.:
20160709 14:07:20
wth!!! exponential passes in 0.00s 

GAURAV CHANDEL:
20160428 11:25:24
Be Happy .. with DP .. 

kejriwal:
20160116 17:49:31
solve to increase your confidence in dp :) ! 

hodobox:
20151229 02:59:25
Solved it as knapsack in O( (BiAi)*n*m ) 

Prateek Agarwal:
20151204 08:58:35
No memoization required 

spoj2121:
20151201 17:43:28
weak test case backtracking gets AC in 0.00 sec..


Saksham :
20150813 00:49:58
Nice one 

sarvagya:
20150807 02:24:40
learnt a lot about dp with this ! 0.00 AC :D 
Added by:  Ankit Kumar Vats 
Date:  20111021 
Time limit:  0.490s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Inspired 