#include <bits/stdc++.h>


using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int nmax=10010;
int g,n,p[nmax],w[nmax],v[2][nmax],ans;

int main(){
in >>n>>g;
for(int i=1;i<=n;++i){
	in >>w[i]>>p[i];
}
int l=0;
for(int i=1;i<=n;++i,l=1-l){
	for(int ww=0;ww<=g;++ww){
		v[1-l][ww]=v[l][ww];
		 if(w[i]<=ww){
			v[1-l][ww]=max(v[1-l][ww],v[l][ww-w[i]]+p[i]);
		}
		
	}
}
ans =v[l][g];
out <<"\n"<<ans;
return 0;
}