#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,g1,i,j,maxi,max1,a[5001],b[5001],v[100001];
int main()
{f>>n>>g1;
for(i=1;i<=n;++i)
	f>>a[i]>>b[i];
maxi=0;
max1=0;
v[0]=1;
for(i=1;i<=n;++i)
{for(j=maxi;j>=1;--j)
	if(v[j]!=0)
		{if(v[j+a[i]]<v[j]+b[i]&&j+a[i]<=g1)
		{v[j+a[i]]=v[j]+b[i];
		if(j+a[i]>maxi)
			maxi=j+a[i];
		if(v[j+a[i]]>max1)
			max1=v[j+a[i]];
		}}
		
			
if(v[a[i]]<b[i])
	v[a[i]]=b[i];
if(a[i]>maxi)
	maxi=a[i];
if(v[a[i]]>max1)
	max1=v[a[i]];
}
g<<max1<<'\n';
f.close();
g.close();
return 0;
}