#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[2][10005], g[10005], p[10005], n, G;

int main()
{
	int i, j, l=1;
	fin >> n >> G;
	for (i = 1; i <= n; i++)
		fin >> g[i] >> p[i];
	for (i = 1; i <= n; i++)
	{	
		l = 1 - l;
		//? Cum stiu ca nu am depasit greutatea maxima?
		//Pt ca am aia cu j-g[i] si daca e cu - inseamna ca se pune direct 1-l,j; contrar inseamna ca mai incap obiecte
		//? Dc nu e stabilit 1 sau 0 dinainte si dc trebuie sa merg oarecum zig zag?
		//Fac schema cu zig zag ca sa pot sa tin minte valorile maxime trecute si sa la inlocuiesc cand gasesc val mai mari
		for (j = 0; j <= G; j++)
		{
			dp[1-l][j] = dp[l][j];
			if (g[i] <= j)
				dp[1-l][j] = max(dp[l][j - g[i]] + p[i], dp[1-l][j]);
		}
	}
	//Raspunsul o sa fie in G(evident) si in functie de cate nr sunt presimt ca conteaza daca e pe 0 sau 1
	fout << max(dp[0][G],dp[1][G])<<"\n";
	return 0;
}