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