#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(j>=w)
				v[i&1][j]=max(v[(i-1)&1][j],v[(i-1)&1][j-w]+p);
		}
	}
	cout<<v[(n&1)][g];
    return 0;
}