#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("rucsac.in","r");
 FILE *fout=fopen("rucsac.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);
return 0;
}