#include<fstream>
using namespace std;
int n,g,v[10100],mx;
int main() {
	int i,x,y,j;
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in>>n>>g;
	v[0]=1;
	for(i=0;i<n;i++) {
		in>>y>>x;
		for(j=min(mx,g-y);j>=0;j--)
			if(v[j]&&v[j+y]<v[j]+x) {
				v[j+y]=v[j]+x;
				if(j+y>mx)
					mx=j+y;
				}
		}
	mx=0;
	for(i=g;i>=0;i--)
		if(v[i]>v[mx])
			mx=i;
	out<<v[mx]-1<<'\n';
	in.close();
	out.close();
	return 0;
}