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
Sanjeev Kumar:
20141016 12:21:11
Last edit: 20141025 16:08:30 

^_^:
20141016 12:18:11
Last edit: 20141016 12:18:24 

californiagurl:
20140214 19:43:05
recursion?


Anand Mishra:
20130914 17:59:38
Legen......wait for it................still waiting......


on the hell:
20130410 13:52:00
even bactracking goes ...


ALI HASAN:
20121204 13:26:33
Very nice problem 

Archit Mittal:
20120722 08:24:46
easy one... 

Hussain Kara Fallah:
20120114 01:44:57
Last edit: 20120114 01:57:57 

shubhang singh chauhan:
20120104 11:48:04
very weak test cases, make them hard


[ !0 ]:
20111126 18:37:40
@madhav both identical and same :) 
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 