#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int i,gmax,n,g[5001],c[5001],cmax[5001],maxx;
char viz[1001][5001];
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 && viz[i-g[j]][j]==0 && cmax[i-g[j]]>0) || g[j]==i)
                if(c[j]+cmax[i-g[j]]>maxi)
                {
                    maxi=c[j]+cmax[i-g[j]];
                    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;
}