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
Abhishek:
2014-12-12 17:49:08
Any of Recursion and Backtracking will do. |
|
californiagurl:
2014-02-14 19:43:05
recursion?
|
|
Anand Mishra:
2013-09-14 17:59:38
Legen......wait for it................still waiting......
|
|
on the hell:
2013-04-10 13:52:00
even bactracking goes ...
|
|
ALI HASAN:
2012-12-04 13:26:33
Very nice problem |
|
Archit Mittal:
2012-07-22 08:24:46
easy one... |
|
shubhang singh chauhan:
2012-01-04 11:48:04
very weak test cases, make them hard
|
|
[ !0 ]:
2011-11-26 18:37:40
@madhav- both identical and same :) |
|
:-P:
2011-11-10 16:15:45
this problem is legen --wait for it---
|
|
madhav:
2011-11-02 13:49:06
should the N gifts be treated identical or same? |
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 |