#include<iostream>
#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
#define MAXN 5010 
#define MAXG 10010 
int W[MAXN],P[MAXN],D[2][MAXG];
int main(){
int i,cw,N,G,l=0;
f>>N>>G;
for(i=1;i<=N;i++){
	f>>W[i]>>P[i];
}
for(i=1;i<=N;i++, l=1-l){
	for(cw=0;cw<=G;cw++){
		D[1-l][cw]=D[l][cw];
		if(W[i]<=cw && D[l][cw-W[i]]+P[i]>D[1-l][cw]){
			D[1-l][cw]=D[l][cw-W[i]]+P[i];
		}
	}
}
g<<D[l][G];
f.close();
g.close();
return 0;
}