#include<cstdio>
using namespace std;
int cmax[5000]={-1},uz[5000][5000],n,G,c[5000],g[5000],k,i,s;
FILE *f,*h;
void citire()
{
    fscanf(f,"%d %d",&n,&G);
    for(int i=1; i<=n; i++)
        fscanf(f,"%d %d",&g[i],&c[i]);
}
void rezolva()
{
    cmax[0]=0;
    for(s=1; s<=G; s++)
        for(i=1; i<=n; i++)
        if(g[i]<=s && !uz[s-g[i]][i] && cmax[s-g[i]]!=-1)
        if(cmax[s]<cmax[s-g[i]]+c[i])
    {
        cmax[s]=cmax[s-g[i]]+c[i];
        for(k=1; k<=n; k++)
            uz[s][k]=uz[s-g[i]][k];
        uz[s][i]=1;
    }

}
int main()
{
    f=fopen("rucsac.in","r");
    h=fopen("rucsac.out","w");
    citire();
    rezolva();
    fprintf(h,"%d",cmax[G]);
}