#include<fstream>
#include<iostream>
//#include<algorithm>
using namespace std;
int n, gr[10010], pr[10010], m[10010][50010], mx, g, m1;
ifstream f("in");
ofstream o("rucsac.out");

int main(){
f>>n>>g;
for(int i=1;i<=n;++i) f>>gr[i]>>pr[i], cout<<pr[i]<<' ';
for(int j=1; j<=n; ++j){
	for(int i=0;i<=g;++i){
	//	for(int k=0; i-gr[k]>0; ++k)
            m[i][j]=m[i][j-1];
			if(i>=gr[j]&&m[i-gr[j]][j-1]+pr[j]>m[i][j]) m[i][j]=m[i-gr[j]][j-1]+pr[j];
		//m[i][j]=max(m[i][j-1],m1);
	}
}
o<<m[g][n];
o.close();
return 0;
}