#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=1;ww<=g;ww++){
		
		 if(w[i]<=ww){
			v[1-l][ww]=max(v[l][ww],v[l][ww-w[i]]+p[i]);
		}else v[1-l][ww]=v[l][ww];
		
	}
}
out <<v[l][g];

}