#include <stdio.h>

using namespace std;

FILE*f=fopen("rucsac.in","r");
FILE*h=fopen("rucsac.out","w");
int g[5010],c[5010],cmax[10010],use[10010][5010];
//complexitate n*gmax
int main()
{
    int n,gmax,i,j,mx,sol,pu,ii;
    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];
                for (ii=1;ii<=n;ii++) use[j+g[i]][ii]=use[j][ii];
                use[j+g[i]][i]=1;
                if (j+g[i]>mx) mx=j+g[i];
            }
    sol=0;
    for (i=0;i<=gmax;i++)
        if (cmax[i]>sol) {sol=cmax[i];pu=i;}
    fprintf(h,"%d\n",sol);
    //for (i=1;i<=n;i++) if (use[pu][i]) fprintf(h,"%d ",i);
    fclose(h);
    fclose(f);
    return 0;
}