#include <fstream>

using namespace std;

#define maxG 10005
#define maxN 5005

int sol, best[2][maxG], W[maxN], P[maxN];


int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	
	int N, G;
	
	f >> N >> G;
	
	for (int i = 1; i <= N; ++ i) f >> W[i] >> P[i];
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= G; ++ j)
		{
			int l = i % 2;
			
			if (j - W[i] >= 0) best[l][j] = max (best[! l][j], best[! l][j - W[i]] + P[i]);
			else best[l][j] = best[! l][j];
		}
	
	
	g << best[N % 2][G];

	return 0;
}