#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int i,j,N,W,**C,*v,*w,v1,w1;
  
  if (scanf("%d %d",&N,&W)<2) exit(1);
  C = malloc((N+1)*sizeof(int*));
  for (i=0;i<N+1;i++) C[i] = malloc((W+1)*sizeof(int));
  for (i=0;i<N+1;i++) {
    for (j=0;j<W+1;j++) C[i][j] = 0;
  }
  
  v = malloc((N+1)*sizeof(int));
  w = malloc((N+1)*sizeof(int));
  for (i=1;i<N+1;i++) {
    if (scanf("%d %d",&v1,&w1)<2) exit(1);
    v[i] = v1; w[i] = w1;
  }
  
  for (i=1;i<N+1;i++) {
    for (j=1;j<W+1;j++) {
      if (j < w[i]) {
        C[i][j] = C[i-1][j];
        continue;
      }
      if (C[i-1][j] > C[i-1][j-w[i]]+v[i]) C[i][j] = C[i-1][j];
      else C[i][j] = C[i-1][j-w[i]]+v[i];
    }
  }
  
  printf("%d\n",C[N][W]);
  
  return 0;
}