#include<stdio.h>
int main(void)
{
  int N,W,i,j;
  scanf("%d%d",&N,&W);
  int v[N],w[N];
  for(i=0;i<N;i++){
    scanf("%d%d",&v[i],&w[i]);
  }
  int Nap[W+1][N];
  for(i=0;i<=W;i++){
    if(i-w[0]>=0) Nap[i][0]=v[0];
    else Nap[i][0]=0;
    //printf("%d ",Nap[i][0]);
  }
  for(j=1;j<N;j++){
    for(i=0;i<=W;i++){
      int x=0,y=0,max;
      x=Nap[i][j-1];
      if(i-w[j]>=0) y=Nap[i-w[j]][j-1]+v[j];
      if(x>y) max=x;
      else max=y;
      Nap[i][j]=max;
    }
  }
/*  for(j=0;j<N;j++){
    for(i=0;i<=W;i++){
      printf("%d ",Nap[i][j]);
    }
    printf("\n");
  }*/
   printf("%d\n",Nap[W][N-1]);
  return 0;
}

