#include<fstream>
using namespace std;

int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");

	// n = nr. obiecte, g = greutatea maxima, l1 = linie 1, l2 = linie 2, w = weight, p = profit
	int n, g, *l1, *l2, *aux, *w, *p, i, j; 
	fin >> n >> g;
	l1 = new int[g + 1]; // de la 1 la g
	l2 = new int[g + 1];
	w = new int[n + 1];
	p = new int[n + 1];
	for(i = 0; i <= g; i++)
	{
		l1[i] = 0;
		l2[i] = 0;
	}
	for(i = 1; i <= n; i++)
		fin >> w[i] >> p[i];
	for(i = 1; i <= n; i++)
	{
		for(j = 0; j <= g; j++)
		{
			l2[j] = l1[j];
			if(j >= w[i] && l1[j] < (l1[j - w[i]] + p[i]))
				l2[j] = l1[j - w[i]] + p[i];
		}
		aux = l1;
		l1 = l2;
		l2 = aux;
	}
	fout << l1[g];
	return 0;
}