#include <iostream>
#include <cstdio>

using namespace std;

#define maxG 10005
#define maxN 5005

int sol, best[2][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)
	{	
		int l = i % 2;
		
		for (int j = 1; j <= G; ++ j)
			if (j >= W[i]) best[l][j] = max (best[! l][j], best[! l][j - W[i]] + P[i]);
			else best[l][j] = best[! l][j];
	}
	
	
	printf ("%d", best[N % 2][G]);

	return 0;
}