#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[MAXG][MAXG];
int main(){
int i,cw,N,G;
f>>N>>G;
for(i=1;i<=N;i++){
	f>>W[i]>>P[i];
}
for(i=1;i<=N;i++){
	for(cw=0;cw<=G;cw++){
		D[i][cw]=D[i-1][cw];
		if(W[i]<=cw && D[i-1][cw-W[i]]+P[i]>D[i][cw]){
			D[i][cw]=D[i-1][cw-W[i]]+P[i];
		}
	}
}
g<<D[N][G];
f.close();
g.close();
return 0;
}