int main(void){
  
  int i,j,k,n,w1;
  int v[100],w[100];
  int *last,*next,*temp;

  scanf("%d %d",&n,&w1);
  for(i=0;i<n;i++) scanf("%d %d",&v[i],&w[i]);

  w1++;
  last=(int *)calloc(w1,sizeof(int));
  next=(int *)calloc(w1,sizeof(int));

  for(i=0;i<w1;i++){
    last[i]=0;
    next[i]=0;
  }

  for(i=0;i<n;i++){
    for(j=0;j<w1;j++){
      if(j-w[i]>=0 && next[j-w[i]]+v[i]>last[j]){
	next[j]=next[j-w[i]]+v[i];
      }
      else{
	next[j]=last[j];
	  }
    }
    last=temp;
    last=next;
    next=temp;
  }

  printf("%d\n",next[j]);
  return 0;
}