#include<string.h>
#include<stdio.h>
#define maxn 5001
#define maxg 10001
int greutate[maxn],profit[maxn],opt[maxg];
int i,j,n,g,sol;
int main()
{
 FILE *fin=fopen("rucsac1.in","r");
 FILE *fout=fopen("rucsac1.out","w");
 fscanf(fin,"%d %d",&n,&g);
 for(i=1;i<=n;i++)
     {
	  fscanf(fin,"%d %d",&greutate[i],&profit[i]);
     }
 opt[0]=0;
 for(i=1;i<=n;i++)
	 for(j=g-greutate[i];j>=0;j--)
	     {
		  if(opt[j+greutate[i]]<opt[j]+profit[i])
             {
		      opt[j+greutate[i]]=opt[j]+profit[i];
		      if(opt[j+greutate[i]]>sol)
			     sol=opt[j+greutate[i]];
             }
         }
 fprintf(fout,"%d",sol);
fclose(fin);
fclose(fout);
return 0;
}