#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
#define MAXN 5001
#define MAXG 10010
int N,G,W[MAXN],P[MAXN],D[2][MAXG];
int main() {
	int i,w,l;
	cin>>N>>G;
	for(i=1;i<=N;i++)
	    cin>>W[i]>>P[i];
	l=0;    
    for(i=1;i<=N;i++,l=1-l)
       for(w=0;w<=G;w++) {
			 D[1-l][w]=D[l][w];
			 if(W[i]<=w) 
			   D[1-l][w]=max(D[1-l][w],D[l][w-W[i]]+P[i]);
    }
	cout<<D[l][G];		   		   
	return 0;
}