#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(){
in >>n>>g;
for(int i=1;i<=n;i++){
	in >>w[i]>>p[i];
}
for(int i=1;i<=n;i++){
	for(int ww=1;ww<=g;ww++){
		
		 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];
		
	}
}
out <<v[n][g];

}