#include <fstream>

using namespace std;

const int NMAX = 5000;

int N,G;
int weight[NMAX], profit[NMAX];
int value[2*NMAX];

void scan() {
	ifstream in("rucsac.in");
	in>>N>>G;
	for (int i = 0; i < N; ++i) {
		in>>weight[i]>>profit[i];
	}
	in.close();
}

void initialize() {
  for (int i = 1; i <= G; i++) {
    value[i] = -1;
  }
}

int dinamica() {
  int maxWeight = 0;
  int maxValue = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = maxWeight; j >= 0; j--) {
      if (value[j] != -1 && j + weight[i] <= G) {
          if (value[j + weight[i]] < value[j] + profit[i]) {
            value[j + weight[i]] = value[j] + profit[i];
            if (maxValue < value[j + weight[i]]) maxValue = value[j + weight[i]];
            if (j + weight[i] > maxWeight) maxWeight = j + weight[i];
          }
        }
      }
    }
  return maxValue;
}

void output() {
	ofstream out("rucsac.out");
	out<<dinamica();
	out.close();
}

int main() {
	scan();
  initialize();
  output();
	return 0;
}