#include <stdio.h>
#include <stdlib.h>
#define maxim(a, b) ((a > b) ? a : b )
int w[5001], p[5001];
int d[5001][10001];
int main(){
  int n, g, i, j;
  FILE *fin, *fout;
  fin=fopen("rucsac.in", "r");
  fout=fopen("rucsac.out", "w");
  fscanf(fin, "%d%d", &n, &g);
  for(i=1; i<=n; i++)
    fscanf(fin, "%d%d", &w[i], &p[i]);
  for(i=1; i<=n; i++)
    for(j=0; j<=g; j++)
      if(w[i]>j)
        d[i][j]=d[i-1][j];
      else
        d[i][j]=maxim(d[i-1][j], d[i-1][j-w[i]]+p[i]);
  fprintf(fout, "%d", d[n][g]);
  fclose(fin);
  fclose(fout);
    return 0;
}