#include <stdio.h>

using namespace std;

FILE*f=fopen("rucsac.in","r");
FILE*h=fopen("rucsac.out","w");

//complexitate n*gmax
int main()
{
    int n,gmax,i,j,mx,cmax[10001]={0},sol,g[5001],c[5001];
    fscanf(f,"%d%d",&n,&gmax);
    for (i=1;i<=n;i++) fscanf(f,"%d%d",&g[i],&c[i]);

    cmax[0]=0;
    mx=0;
    for (i=1;i<=n;i++)
        for (j=mx;j>=0;j--)
            if (cmax[j+g[i]]<cmax[j]+c[i]&&j+g[i]<=gmax&&(!j||cmax[j]))
            {
                cmax[j+g[i]]=cmax[j]+c[i];
                if (j+g[i]>mx) mx=j+g[i];
            }
    sol=0;
    for (i=0;i<=gmax;i++)
        if (cmax[i]>sol) sol=cmax[i];
    fprintf(h,"%d",sol);
    fclose(h);
    fclose(f);
    return 0;
}