#include <fstream>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int max(int ,int );
int a[5000],b[5000];
int v[2][10006];
int main()
{
    int n,g,i,j;
    fin>>n>>g;


    for(i=1;i<=n;i++)
    {
        fin>>a[i]>>b[i];
        //gmax=gmax+a[i].greutate;
        //fout<<a[i].greutate<<" "<<a[i].profit<<"\n";
    }
    for (i=0;i<g;i++)
    {
        v[0][i]=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=g;j++)
        {
            if(j>=a[i])
                v[1][j]=max(v[0][j],v[0][j-a[i]]+b[i]);
            else
                v[1][j]=v[0][j];

        }
        for(j=0;j<=g;j++)
        {
            v[0][j]=v[1][j];
            v[1][j-1]=0;
        }
    }
    fout<<v[1][g];



    return 0;
}
int max (int a , int b )
{
    if (a>=b)
        return a;
    return b;
}