#include <bits/stdc++.h>


using namespace std;

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

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

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[l][ww],v[l][ww-w[i]]+p[i]);
		}
		
	}
}
out <<v[l][g];
return 0;
}