#include <iostream>
#include <fstream>

using namespace std;

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

int n, g, w[5002], p[5002], d[2][10002];

int main () 
{ 
fin >> n >> g;
for (int i = 1; i <= n; i++){
    fin >> w[i] >> p[i];
}
int linie = 0;
for (int i = 1; i <= n; i++){
	  linie = 1 - linie;
	  for (int j = 1; j <= g; j++){
		  d[linie][j] = d[1 - linie][j];
		  if (w[i] <= j)d[linie][j] =max (d[linie][j], d[1 - linie][j - w[i]] + p[i]);
	    }
}
fout << d[linie][g];
return 0;
}