#include <iostream>
#include <fstream>
#define nmax 5005
#define gmax 10005
using namespace std;

int dp[nmax][gmax];		//v[i][j] -> primele i obiecte, greutatea maxima j
int main() {
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	

	int n, G, i, j, w[nmax], p[nmax];
	
	
	f>>n>>G;
	
	for(i=1; i<=n; i++) {
		f>>w[i]>>p[i];
	}
	
	for(i=0; i<=G; i++) dp[0][i] = 0;	//0 obiecte -> profit maxim 0
	
	for(i=1; i<=n; i++) {
		
		for(j=0; j<=G; j++) {
			
				dp[i][j] = dp[i-1][j];
				
				if(w[i]<=j)				//daca incape
					dp[i][j] = max( dp[i][j], p[i] + dp[i-1][j-w[i]] );
			
		}
	}
	
/*	for(i=0; i<=n; i++) {
		for(j=1; j<=G; j++) {
			g<<dp[i][j]<<" ";
		}
		g<<"\n";
	}
*/
	g<<dp[n][G]<<"\n";
	
	f.close();
	g.close();
	return 0;
}