#include<fstream>
#include<algorithm>
using namespace std;

int n,gr,w[10001],p[10001],i,k,v[2][10001],j;


int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	f>>n>>gr;
	for (i=0;i<n;i++) f>>w[i]>>p[i];
	k=1;
	for (i=0;i<n;i++)
	{
        k=1-k;
		for (j=0;j<=gr;j++)
		{
			v[1-k][j]=v[k][j];
			if (w[i]<=j)
			{
				v[1-k][j]=max(v[1-k][j],v[k][j-w[i]]+p[i]);
			}
		}
	}
	g<<v[k][gr];
	f.close();
	g.close();
	return 0;
}