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

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct hot {
  int g, val;
};

void citire(hot v[], int &n, int &G) {
  int i;
  fin >> n >> G;
  for (i = 1; i <= n; i++) fin >> v[i].g >> v[i].val;
}

void gridi(hot v[], int n, int g) {
  int d[10005], ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = g; j - v[i].g >= 0; j--) {
      d[j] = max(d[j], d[j - v[i].g] + v[i].val);
      ans = max(ans, d[j]);
    }
  fout << ans;
}
int main() {
  int n, G;
  hot v[5001];
  citire(v, n, G);
  gridi(v, n, G);
  return 0;
}