#include<fstream>
#include<iostream>
using namespace std;
int n,g,w[5010],p[5010],a[10010],b[10010];

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in>>n>>g;
	for(int i=1;i<=n;i++)
	{
		in>>w[i]>>p[i];
	}
	in.close();
	/*for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=g;j++)
		{
			a[i][j]=a[i-1][j];
			if(j>=w[i])
			{
				a[i][j]=max(a[i-1][j], a[i-1][j-w[i]]+p[i]);
			}
		}
	}*/
	
	for(int i=1;i<=n;i++)
	{
		if(i%2==1)
		{
			for(int j=0;j<=g;j++)
			{
				a[j]=b[j];
				if(j>=w[i])
					{
						a[j]=max(b[j], b[j-w[i]]+p[i]);
					}
			}
		}
		else
		{
			for(int j=0;j<=g;j++)
			{
				b[j]=a[j];
				if(j>=w[i])
					{
						b[j]=max(a[j], a[j-w[i]]+p[i]);
					}
			}
		}
	}
	if(n%2==1)
	out<<a[g];
	else
		out<<b[g];
	return 0;
}