Problem F
Cricket Ranking
Input: standard input
Output: standard output
Time Limit: 2 seconds
World Cup Cricket 2003 is now going on in South Africa. The final will be held on 23rd March in Johannesburg during the grand occasion in Beverly Hills, California.
Fig : New Wanderers Stadium, Johannesburg.
Many of you may not be interested in cricket, but its really a passion in Indian subcontinent. Ranking of cricketers is a common pheonomenon there. Cricketers are ranked by their performance in both form of cricket ( Test and Oneday). People really enjoy this ranking. They like to see their favourite players as top ranked. They will not be happy if they see Matthew Hayden as top ranked in stead of Sachin Tendulkar or Rahul Dravid. Currently many such rankings are available. And as you have probably guessed, each ranking makes a different player as top ranked.
World Cup committee has decided that they will make a new ranking on the performance of players in the world cup. They want the ranking to be acceptable to the public. The rules are as follows :
There are K different departments. Cricketers will be given points in each department depending on their performance.
The maximum points for each department are not euqal. Such as Saeed Anwar can get maximum 25 points in batting but Jonty Rhodes can get maximum 10 points for his spectacular fielding.
The sum of maximum points of all departments will be exactly N points. And the final ranking will depend on the total earned points out of N points.
The ranking committee wants popular cricketers get top ranked. To do so they even allow maximum points for fielding more than that of batting. But that can bring lots of criticism. So they decide to fix a range of points for each department. Such as maximum points for batting will be atleast 10 and atmost 15 or for fielding, it will be atleast 8 and atmost 12. But the total points will be 20. Then 3 ranking system is possible, such as :
| Batting | Fielding |
|---|---|
| 10 | 10 |
| 11 | 9 |
| 12 | 8 |
In this problem, you have to find out the number of ranking systems possible for given number of departments, range of points for each department and total points.
Input
Each dataset starts with two positive integer K(1<=K<=7) and N(1<=N<=2000000000). In next few lines there will be 2K positive integers which will successively denote the lower and upper limit of allowable maximum points for each department. Input is terminated by EOF. There may be as many as 500 datsets.
Output
For each input print the total number of ranking systems possible maintaining the given constraints. The final answer can be as large as 60-digits.
Sample Input
Sample Output