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

#define NMAX 5000

struct obiect {
  int g;
  int pr;
};
struct obiect v[NMAX+1];

int d[2][NMAX*2+1];
int GMAX=10000;

int max (int a,int b){
  if(a>b){
    return a;
  }
  return b;
}

int main() {

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

  int n,G,i,j;
  fscanf(fin,"%d%d",&n,&G);
  for(i=1;i<=n;i++){
    fscanf(fin,"%d%d",&v[i].g,&v[i].pr);
  }
  for(i=1;i<=n;i++){
    for(j=v[i].g;j<=GMAX;j++){
      //if(d[(i-1)%2][j-v[i].g]!=0)
        d[i%2][j]=max(d[(i-1)%2][j-v[i].g]+v[i].pr,d[(i-1)%2][j]);
    }
  }

  fprintf(fout,"%d",d[n%2][G]);

  fclose(fin);
  fclose(fout);
  return 0;
}