填空题

美丽的项链

Question

妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。

于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:

1、需要使用n种特定的水晶宝珠

2、第i种水晶宝珠的数量不能少于l_i颗, 也不能多于r_i颗

3、一条美丽的项链由m颗宝珠组成

妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。

输入描述：

输入包括n+1行, 第一行包括两个正整数(1 <= n <= 20, 1 <= m <= 100), 表示水晶宝珠的种数和一条美丽的项链需要的水晶宝珠的数量。

接下来的n行, 每行两个整数l_i, r_i(0 <= l_i <= r_i <= 10), 表示第i种宝珠的数量限制区间。

输入样例： 3 5 0 3 0 3 0 3 输出描述： 输出一个整数, 表示满足限定条件的方案数。保证答案在64位整数范围内。输出样例 12