#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
int c[5001],gr[5001],cmax[2][10001];
int main ()
{
	int n,i,gmax,s,l;
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	f>>n>>gmax;
	for(i=1;i<=n;i++)
		f>>gr[i]>>c[i];
	f.close();
	l=0;
	for(i=1;i<=n;i++,l=1-l)
		for(s=0;s<=gmax;s++) {
			cmax[1-l][s]=cmax[l][s];
			if((gr[i]<=s)&&(cmax[1-l][s]<(cmax[l][s-gr[i]]+c[i])))
				cmax[1-l][s]=cmax[l][s-gr[i]]+c[i];
		}
	g<<cmax[l][gmax];
	return 0;
}