#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int n, Gmax, c[5001],g[5001], use[5001][10001],cmax[10001], rez;

int main()
{
    int s, i, k ;

    fin>>n>>Gmax;
    for(i=1;i<=n;i++)
        {fin>>g[i];
        fin>>c[i];}

    cmax[0]=0;
    for(i=1;i<=Gmax;i++)
        cmax[i]=-1;
   rez=0;
    for(s=1;s<=Gmax;s++)
        for(i=1;i<=n;i++)
            if(g[i]<=s &&cmax[s-g[i]]!=-1 && use[s-g[i]][i]==0)
                if(cmax[s]<cmax[s-g[i]]+c[i])
                {
                    cmax[s]=cmax[s-g[i]]+c[i];
                    if(rez<cmax[s])rez=cmax[s];
                    for(k=1;k<=n;k++)
                        use[s][k]=use[s-g[i]][k];
                    use[s][i]=1;
                }
    //int gata=0;

    fout<<rez;
    fout.close();
    return 0;
}