http://acm.hdu.edu.cn/showproblem.php?pid=2152
//1307251 2009-04-25 10:56:01 Accepted 2152 0MS 260K 527 B C++ no way 
#include<iostream>
using namespace std;
int main()
{
    int n,M;
    while(cin>>n>>M)
    {
        int i,j,k;
        int most[101],least[101],num[101],temp[101];
        for(i=1;i<=n;i++)
            cin>>least[i]>>most[i];
        for(i=0;i<=M;i++)
            temp[i] = num[i] = 0;
        num[0] = 1;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=M;j++)
            {
                for(k=least[i];k<=most[i] && k+j<=M;k++)
                    temp[j+k] += num[j];
            }
            for(j=0;j<=M;j++)
            {
                num[j] = temp[j];
                temp[j] = 0;
            }
        }
        cout<<num[M]<<endl;
    }
    return 0;
}