#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[MAXN][MAXG];
int main() {
	int i,w;
	cin>>N>>G;
	for(i=1;i<=N;i++)
	    cin>>W[i]>>P[i];
	for(i=1;i<=N;i++)
	      for(w=0;w<=G;w++) {
		  	D[i][w]=D[i-1][w];				
	       if(W[i]<=w)
		   		D[i][w]=max(D[i][w],D[i-1][w-W[i]]+P[i]);
     }
    cout<<D[N][G];
	return 0;
}