#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,x;
    for(i=1;i<=gmax;i++)
    {
        maxi=0;
        for(j=1;j<=n;j++)
        {
            if(g[j]<=i )
            {
                x=i-g[j];
                if(viz[x][j]==0)
                    if(cmax[i-g[j]]>0)
                        if(c[j]+cmax[i-g[j]]>maxi)
                        {
                            maxi=c[j]+cmax[i-g[j]];
                            pmax=j;
                        }
            }
            if(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;
}