#include<fstream>
#define e endl
#define FOR(a,b,c) for(int a=(b); a<=(c); ++a)
#define TOR(a,b) for(int a=0; a<(b); ++a)
#define ROR(a,b,c) for(int a=(b); a>=(c); --a)
using namespace std;

					fstream f("rucsac.in");
					ofstream t("rucsac.out");
					
struct RUC{
	int GR, profit;
};
					
													int N, G, S, A[10001];
													RUC Q[10001];
int main(){
	
	f>>N>>G;
	
	FOR(i,1,N){
		f>>Q[i].GR>>Q[i].profit;
	}
     
    
    
    FOR(i,1,N)
	   for(int j = G-Q[i].GR; j>=0; --j){
	   		if(A[j+Q[i].GR] < A[j] + Q[i].profit){
	   			A[j+Q[i].GR] = A[j] + Q[i].profit;
	   			if(A[j+Q[i].GR] > S) 
	   				S = A[j+Q[i].GR];
			   }
		   }
		   
    /*FOR(i,1,N)
        for( int j = G - W[i]; j >= 0; --j) {
            if( Q[j+W[i]] < Q[j] + P[i] )
            {
                Q[j+W[i]] = Q[j] + P[i];
                if( Q[j+W[i]] > S)
                    S = Q[j+W[i]];
            }ROR(j,G-Q[i].GR,0)
            	for(int j = G-Q[i].GR; j>=0; --j)
        }*/

	t<<S;
	
	return 0;
}