#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int val[5002];
int g[5002];
int best[10002];
bool ap[10002];

int main (){

  int n, smax;
  fin >> n >> smax;
  for (int i = 1; i <= n; ++i)
      fin >> g[i] >> val[i];

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

}