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

#define MAX_N 5000
#define MAX_G 10000

int w[MAX_N+1], p[MAX_N+1];
int optim[MAX_G+1];

int main()  {

  FILE *in  = fopen("rucsac.in","r");
  FILE *out = fopen("rucsac.out", "w");

  int n, g;
  fscanf(in,"%d %d", &n, &g);

  int i;
  for ( i = 1; i <= n; i++ )
    fscanf(in,"%d %d",&w[i], &p[i]);

  optim[0] = 0;
  int sol = 0;

  int j;
  for ( i = 1; i <= n; i++ )
    for ( j = g - w[i]; j >= 0; j-- ) {
      if ( optim[ j + w[i] ] < optim[j] + p[i] ){
        optim[ j + w[i] ] = optim[j] + p[i];
        if ( optim[ j + w[i] ] > sol )
          sol = optim[ j + w[i] ];
      }
    }

  fprintf(out,"%d",sol);

  fclose(in);
  fclose(out);

  return 0;
}