#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int i,gmax,n,g[5001],c[5001],cmax[5001],viz[5001][1501],maxx;
void rucsac()
{
    int i,j,maxi,pmax;
    for(i=1;i<=gmax;i++)
    {
        maxi=0;
        for(j=1;j<=n;j++)
            if((g[j]<=i && viz[i-g[i]][j]==0 && cmax[i-g[i]]>0)||g[j]==i)
                if(c[j]+cmax[i-g[i]]>maxi)
                {
                    maxi=c[j]+cmax[i-g[i]];
                    pmax=j;
                }
        if(maxi>0)
        {
            for(j=1;j<=n;j++)
                viz[i][j]=viz[i-g[pmax]][j];
            viz[i][pmax]=1;
            cmax[i]=maxi;
        }
    }
}
int main()
{
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    rucsac();
    for(i=1;i<=gmax;i++)
        if(cmax[i]>maxx)
            maxx=cmax[i];
    fout<<maxx;
    return 0;
}