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

int a[gmax], b[gmax];		//v[i][j] -> primele i obiecte, greutatea maxima j; folosesc doar ultimele 2 linii
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++) a[i] = 0, b[i] = 0;	//0 obiecte -> profit maxim 0
	
	for(i=1; i<=n; i++) {
		for(j=0; j<=G; j++) {
			
				b[j] = a[j];	//nu il pun (presupun ca nu incape), si iau rezultatul anterior
				
				if(w[i]<=j)				//daca incape
					b[j] = max( b[j], p[i] + a[j-w[i]] );
			
		}
		
		for(j=0; j<=G; j++) a[j] = b[j];
	}
	
	g<<b[G]<<"\n";
	
	f.close();
	g.close();
	return 0;
}