#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[nmax][nmax];

int main(){
cin >>n>>g;
for(int i=1;i<=n;i++){
	cin >>w[i]>>p[i];
}
for(int i=0;i<=n;i++){
	for(int ww=0;ww<=g;ww++){
		if(i==0 || ww==0){
			v[i][ww]=0;
		}else if(w[i]<=ww){
			v[i][ww]=max(v[i-1][ww],v[i-1][ww-w[i]]+p[i]);
		}else v[i][ww]=v[i-1][ww];
		
	}
}
cout <<v[n][g];

}