#include <iostream>
#include <fstream>
using namespace std;
/*
ifstream fin("spectacole.in");
ofstream fout("spectacole.out");
*/
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
	/*
	int n,i,j,ora,minut,s[101],f[101],poz[101],aux;
	fin >> n;
	for (i=1;i<=n;++i)
	{
		poz[i]=i;
		fin >> ora >> minut;
		s[i]=ora*60+minut;
		fin >> ora >> minut;
		f[i]=ora*60+minut;
	}
	for (i=1;i<=n;++i)
	{
		for (j=i+1;j<=n;++j)
		{
			if (f[poz[i]]>f[poz[j]])
			{
				aux=poz[i];
				poz[i]=poz[j];
				poz[j]=aux;
			}
		}
	}
	fout << poz[1] << " ";
	j=1;
	for (i=2;i<=n;++i)
	{
		if (s[poz[i]]>=f[poz[j]])
		{
			fout << poz[i] << " ";
			j=i;
		}
	}
	*/
	int N, G, i, j;
	fin >> N >> G;
	int W[5001], P[5001], sol = 0, a[10001] = { 0 };
	for (i = 1; i <= N; ++i)
	{
		fin >> W[i] >> P[i];
	}
	for (i = 1; i <= N; ++i)
	{
		for (j = G - W[i]; j >= 0; --j)
		{
			if (a[j + W[i]] < a[j] + P[i])
			{
				a[j + W[i]] = a[j] + P[i];
				if (a[j + W[i]] > sol)
				{
					sol = a[j + W[i]];
				}
			}
		}
	}
	fout << sol;
	return 0;
}