#include <stdio.h>
#include <string.h>

int main(void)
{
  int n,v[1001][1001],g[1001],val[1001],gmax;
  memset(v,0,sizeof(v));
  scanf("%d %d",&n,&gmax);
  printf("---%d %d---\n",n,gmax);
  for(int i=1;i<=n;i++)
  {
    scanf("%d %d",&g[i],&val[i]);
  }
   for(int i=1;i<=n;i++)
        for(int j=1;j<=gmax;j++)
            if(j<g[i])
                v[i][j]=v[i-1][j];
            else
                {
                    int v1=v[i-1][j];
                    int v2=val[i]+v[i-1][j-g[i]];
		    if(v1>v2)
		      v[i][j]=v1;
		    else
		      v[i][j]=v2;
                }
  
  
  printf("%d",v[n][gmax]);
  return 0;
}