#include<iostream>
#include<fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main()
{
    int d[5001][5001],i,j,n,G,w[5000],p[5000];
    f>>n>>G;
    for(i=1; i<=n; i++)
        f>>w[i]>>p[i];

    for(j=0; j<G; j++)
        d[0][j]=INT_MAX;
        d[0][0]=0;

    for(i=1; i<=n; i++)
        for(j=0; j<G; j++)
            if(w[i]>j)  d[i][j]=d[i-1][j];
            else
            {
                d[i][j]= d[i-1][j];
                if(d[i-1][j-w[i]]+p[i] >d[i][j] )
                    d[i][j]= d[i-1][j-w[i]]+p[i];
            }

    int maxi=INT_MIN;
    for(i=0; i<=G; i++)
        if(d[n][i]>maxi)
            maxi=d[n][i];
    cout<<maxi;

    return 0;
}