#include <fstream>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

struct obiect
{
    int p, g;
};

int n, g;
obiect o[5009];
int dp[3][10009];

void citire ();
void pd ();

int main()
{
    citire();
    pd();
    return 0;
}

void citire ()
{
    int i;
    fin>>n>>g;
    for(i=1; i<=n; ++i)
        fin>>o[i].g>>o[i].p;
}

void pd ()
{
    int i, j;
    int lcrt=1, lprec=0;
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=g; ++j)
        {
            dp[lcrt][j]=dp[lprec][j];
            if(j-o[i].g>=0 && dp[lcrt][j]<dp[lprec][j-o[i].g]+o[i].p)
                dp[lcrt][j]=dp[lprec][j-o[i].g]+o[i].p;
        }
        lcrt=1-lcrt;
        lprec=1-lprec;
    }
    fout<<dp[lprec][g]<<'\n';
    fout.close();
}