#include <stdio.h>
#include <stdlib.h>
#define MAXN 5000
#define MAXG 10000
  int v[2][MAXG];
  int G[MAXN+1];
  int P[MAXN+1];

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

  int i,n,g,j,a,b;
  fscanf(fin,"%d%d",&n,&g);
  for(i = 1; i <= n; i++){
    fscanf(fin,"%d%d",&G[i],&P[i]);
  }
  for(i = 0; i <= n; i++){
    for(j = 0;j <= g;j++){
      if(i == 0 || j == 0)
        v[1][j] = 0;
      else{
        a = v[0][j];
        if(j-G[i] >= 0)
          b = v[0][j-G[i]] + P[i];
        else
          b = 0;
        if(a>b) v[1][j] = a;
        else v[1][j] = b;
      }
      //printf("%d ",v[1][j]);
    }
    //printf("\n");
    for(j = 0; j <= g;j++)
      v[0][j] = v[1][j];
  }
  fprintf(fout,"%d",v[0][g]);
  return 0;
}