#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
class BigNum
{
vector<int> val;
public:
static const int NUM = 10000;
static const int WIDTH = 4;
BigNum(int n = 0);
friend ostream& operator << (ostream &out, const BigNum &n);
bool operator != (const BigNum &n) const {return val != n.val;}
BigNum& operator += (const BigNum &n2);
};
BigNum::BigNum(int n /* = 0 */)
{
do // 保证val至少有一个元素
{
int a = n / NUM;
int b = n % NUM;
val.push_back(b);
n = a;
} while(n > 0);
}
BigNum& BigNum::operator += (const BigNum &n2)
{
if (val.size() < n2.val.size()) // n2短
val.resize(n2.val.size());
transform(n2.val.begin(), n2.val.end(), val.begin(), val.begin(), plus<int>());
int lastAdd = 0;
for (vector<int>::iterator it = val.begin(); it != val.end(); ++it)
{
*it += lastAdd;
if (*it >= BigNum::NUM)
{
*it -= BigNum::NUM;
lastAdd = 1;
}
else
lastAdd = 0;
}
if (lastAdd == 1)
val.push_back(1);
return *this;
}
ostream& operator << (ostream &out, const BigNum &n)
{
if (n.val.size() == 1) // 只有一个数
return out << n.val[0];
out << n.val.back();
char c = out.fill('0');
for (vector<int>::const_reverse_iterator it = n.val.rbegin()+1;
it != n.val.rend(); ++it)
out << setw(BigNum::WIDTH) << *it;
return out << setfill(c);
}
#if 1 // 记录表法
const int MAX_N = 20;
const int MAX_S = 1000;
int n, S;
int a[MAX_N], b[MAX_N];
BigNum T[MAX_N][MAX_S + 1] = {{0}}; // 记录表
BigNum Cal(int day, int done, int min, int max)
{
int left = S - done; // 还有多少题要做
if (left < min || left > max) // 超出可能的做题范围
return 0; // 方案必不成功，部分方案数为0
if (day == n - 1) // 最后一天，方案必然可能
return 1; // 部分方案数为1，递归终止
if (T[day][done] != 0) // 已经计算过
return T[day][done];
BigNum total = 0; // 部分方案数
for (int t = a[day]; t <= b[day]; t++) // 枚举
total += Cal(day + 1, done + t, min-a[day], max-b[day]); // 递归计算
T[day][done] = total; // 记录下来
return total;
}
int main()
{
// 读入数据
cin >> n >> S;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
int min = 0, max = 0; // 最少和最多做题数量
for (int i = 0; i < n; i++)
{
min += a[i];
max += b[i];
}
cout << Cal(0, 0, min, max) << endl;
return 0;
}
#else // 动态规划算法
const int MAX_N = 20;
const int MAX_S = 1000;
int n, S;
int a[MAX_N], b[MAX_N];
BigNum fa[MAX_N][MAX_S+1];
int main()
{
// 读入数据
cin >> n >> S;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
int leftMin = 0, leftMax = 0; // 还剩下的天中最少和最多做题数
for (int i = 0; i < n; i++)
{
leftMin += a[i];
leftMax += b[i];
}
// 第0天
int realMin = a[0], realMax = b[0]; // 到当前天为止，最少和最多做题数
leftMin -= a[0]; leftMax -= b[0];
if (realMin < S - leftMax) realMin = S - leftMax;
if (realMax > S - leftMin) realMax = S - leftMin;
for (int t = realMin; t <= realMax; t++)
fa[0][t] = 1;
for (int day = 1; day < n; day++)
{
realMin += a[day]; realMax += b[day];
leftMin -= a[day]; leftMax -= b[day];
if (realMin < S - leftMax) realMin = S - leftMax;
if (realMax > S - leftMin) realMax = S - leftMin;
for (int tall = realMin; tall <= realMax; tall++) // 对于总题量
for (int t = a[day]; t <= b[day] && t <= tall; t++)
fa[day][tall] += fa[day-1][tall-t]; // 累计之前的可能方案数
}
cout << fa[n-1][S] << endl;
return 0;
}
#endif
