#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void)
{
  FILE *f=NULL;
  int n,v[3][10005],g[1001],val[1001],gmax;
  memset(v,0,sizeof(v));
  if((f=fopen("rucsac.in","r"))==NULL)
    {
      perror(NULL);
      exit(-1);
    }
  fscanf(f,"%d %d",&n,&gmax);
  for(int i=1;i<=n;i++)
  {
    fscanf(f,"%d %d",&g[i],&val[i]);
  }
  if(fclose(f)!=0)
    {
      perror(NULL);
      exit(-1);
    }
  for(int j=1;j<=gmax;j++)
    if(j<g[1])
      v[1][j]=0;
    else
      {
	int v2=val[1];
	v[1][j]=v2;
      }
  //for(int i=1;i<=gmax;i++)
    //printf("%d la %d\n",i,v[1][i]);
   for(int i=2;i<=n;i++)
     {
        for(int j=1;j<=gmax;j++)
	  {
            if(j<g[i])
                v[2][j]=v[1][j];
            else
                {
                    int v1=v[1][j];
                    int v2=val[i]+v[1][j-g[i]];
		    //printf("--%d-%d--  " ,v1,v2);
		    if(v1>v2)
		      v[2][j]=v1;
		    else
		      v[2][j]=v2;
                }
	  }
	/*for(int h=1;h<=gmax;h++)
	  printf("%d ",v[1][h]);
	printf("\n");
	for(int h=1;h<=gmax;h++)
	  printf("%d ",v[2][h]);
	  printf("\n\n");*/
	for(int h=1;h<=gmax;h++)
	  v[1][h]=v[2][h];
     }
  
  if((f=fopen("rucsac.out","w"))==NULL)
    {
      perror(NULL);
      exit(-1);
    }
  // printf("%d",v[2][gmax]);
  fprintf(f,"%d",v[2][gmax]);
  if(fclose(f)!=0)
    {
      perror(NULL);
      exit(-1);
    }
  return 0;
}