#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,g[5010],p[5010],d[5010],i,j,maxim;
int main() {
	fin>>n>>G;
	for (i=1;i<=n;i++) {
		fin>>g[i]>>p[i];
	}
	d[0]=1;
	for (i=1;i<=n;i++) {
		for (j=G;j>=0;j--) {
			if (d[j]!=0&&j+g[i]<=G)
				d[j+g[i]]=max(d[j+g[i]],d[j]+p[i]);
		}
	}
	for (i=0;i<=G;i++)
		maxim=max(maxim,d[i]);
	fout<<maxim-1;
	return 0;
}