#include <fstream>
using namespace std;

ifstream fi ("rucsac.in");
ofstream fo ("rucsac.out");

const int dim = 5003;
int G, N, P[dim], W[dim], R[dim<<1], O[dim<<1];

void cit ()
{
	fi >> N >> G;
	for (int i = 1; i <= N; i++)
		fi >> W[i] >> P[i];
}

void ruc ()
{
	int i, j;
	for (i = 1; i <= N; i++)
	{
		for (j = G-1; j >= 0; j--)
		{
			if ((R[j] > 0 || j == 0) && j + W[i] <= G)
			{
				if (R[j+W[i]] < R[j] + P[i])
				{
					R[j+W[i]] = R[j] + P[i];
//					O[j+W[i]] = i;					
				}				
			}			
		}
	}
}

void afi ()
{
	fo << R[G] << '\n';
}

int main ()
{
	cit ();
	ruc ();
	afi ();
	return 0;
}