# include <iostream>
# include <cstdio>
using namespace std;

int n , g , w[5005] , p[5005] , best[3][10005] , p_final = 0;

int main ()
{
	freopen ("rucsac.in" , "r" , stdin);
	freopen ("rucsac.out" , "w" , stdout);
	
	scanf ("%d%d" , &n , &g);
	
	for (int i = 1 ; i <= n ; ++i)
		scanf ("%d%d" , &w[i] , &p[i]);
	
	for (int i = 1 ; i <= n ; ++i)
		for (int j = 1 ; j <= g ; ++j)
		{
			
			best[1][j] = best[2][j];
			
			if (w[i] <= j)
				best[2][j] = max (best[1][j] , best[1][j - w[i]] + p[i]);
			
			if (i == n && best[2][j] > p_final)
				p_final = best[2][j];
			
		}
	
	printf ("%d" , p_final);
	
	return 0;
}