#include <fstream>
using namespace std;
const int gmax=1e4;
int v[2][gmax+3];
int main(){
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	int n,g,w,p;
	cin>>n>>g;
	for(int i=1;i<=n;i++){
		cin>>w>>p;
		for(int j=0;j<=g;j++){
			v[i^1][j]=v[(i-1)^1][j];
            if(w<=j){
				v[i^1][j]=max(v[(i-1)^1][j],v[i^1][j-w]+p);
            }
		}
	}
	cout<<v[(n^1)][g];
    return 0;
}