#include<iostream>
#include<fstream>
using namespace std;

#define MAXN 5003
#define MAXG 10003

int w[MAXN], p[MAXN];
int D[MAXN][MAXG];

int main () 
{
  long N, G, i, Pmax;
  
  ifstream in("rucsac.in");
  ofstream out("rucsac.out");
  
 
  in >> N >> G;
  
  for (i = 1; i <= N ; i++) {
      in >> w[i];
      in >> p[i];
  }
  
  for(i = 1; i <= N; i++)
    for(int j = 0; j <= G; j++) {
      
      D[i][j] = D[i-1][j];
      
      if (w[i] <= j )
	  D[i][j] = max( D[i][j], D[i-1][j-w[i]] + p[i]);
    }
  Pmax = D[N][G];
  
  out << Pmax;
  
  in.close();
  out.close();
  
  return 0;
}