#include <bits/stdc++.h>
using namespace std;
int n, sol, gmx, wgt[5002], val[10002], opt[10002];
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main()
{
	in>>n>>gmx;
	for(int i=1;i<=n;i++) in>>wgt[i]>>val[i];
	for(int i=1;i<=n;i++)
		for(int j=gmx-wgt[i];j>=0;j--)
		{
			if(opt[j+wgt[i]]<opt[j]+val[i])
			{
				opt[j+wgt[i]]=opt[j]+val[i];
				if(opt[j+wgt[i]]>sol) sol=opt[j+wgt[i]];
			}
		}
	out<<sol;
}

/*#include<fstream>
 
using namespace std;
 ifstream f("rucsac.in");
 ofstream g("rucsac.out");
int w[5001], p[10001],optim[10001],n,G,i,j,sol;
 
 
int main()
 {
 
    f>>n>>G;
	for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
 
	optim[0] = 0;
 
 
	for( i = 1; i <= n; ++i)
		for( j = G - w[i]; j >= 0; j--)
		{
			if( optim[j+w[i]] < optim[j] + p[i] )
			{
				optim[j+w[i]] = optim[j] + p[i];
				if( optim[j+w[i]] > sol)
					sol = optim[j+w[i]];
			}
		}
	g<<sol;
	return 0;
}*/