#include <iostream>
#include <cstdio>

using namespace std;

#define maxG 10005
#define maxN 5005

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


int main()
{
	freopen ("rucsac.in", "r", stdin);
	freopen ("rucsac.out", "w", stdout);
	
	int N, G;
	
	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)
		{
			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];
			
			if (i == N) sol = max (sol, best[l][j]);
		}
	
	
	printf ("%d", sol);

	return 0;
}