#include <fstream>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int v[5002];
int g[5002];
int d[10002];
bool ap[10002];

int main (){

  int n,gmax;
  int sol = 0;
  fin >> n >> gmax;
  for (int i = 1; i <= n; ++i)
    fin >> g[i] >> v[i];

  d[0] = 0;
  ap[0] = 1;
  for (int i = 1; i <= n; ++i)
  for (int j = gmax-g[i]; j >= 0; --j)
    if (d[j+g[i]] < d[j] + v[i] && ap[j]){
      d[j+g[i]] = d[j] + v[i];
      ap[j+g[i]] = 1;
      if (d[j+g[i]] > sol)
        sol = d[j+g[i]];
    }
   fout << sol;

}