#include <bits/stdc++.h>

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

int n,g,p[5005][10005],i,val,gr,j;

void afis_mat(int linii, int coloane)
{
    int i,j;
    for(i=1; i<=linii; i++)
    {
        for(j=1; j<=coloane; j++)
            fout<<p[i][j]<<' ';
        fout<<'\n';
    }
    fout<<'\n';
}

int main()
{
    fin>>n>>g;
    //afis_mat(n,g);
    fin>>gr>>val;
    p[1][gr]=val;
    for(i=2; i<=n; i++)
    {
        fin>>gr>>val;
        for(j=1; j<=g; j++)
        {
            p[i][j]=p[i-1][j];
            if(gr <= g)
                p[i][j]=max(p[i][j],val+p[i-1][j-gr]);
            //afis_mat(n,g);
        }
    }
    fout<<p[n][g];
    return 0;
}