#include <stdio.h>
int p[6000];
int main ()
{
	int g, w, e[1001],c[1001],i,j,t=0;
	FILE *in=fopen("energii.in","r"), *out=fopen("energii.out","w");
	fscanf(in,"%d%d",&g,&w);
	for(i=0;i<g;i++)
		{
			fscanf(in,"%d%d",&e[i],&c[i]);
			t+=e[i];
		}
	if(t<w){ fprintf(out,"1\n"); return 0; }
	p[0]=1;
    for(i=0;i<g;i++)
        for(j=w-e[i];j>=0;--j)
        {
            if(p[j]&&p[j+e[i]]<p[j]+c[i])
                p[j+e[i]]=p[j]+c[i];
           
        }
	fprintf(out,"%d\n",p[w]-1);
	return 0;
}