#include <cstdio>
#include <algorithm>

using namespace std;

short W[5010], P[5010], n, g;
int a[2][10010];
// in W retin greutatea elementului i
// in P retin pretul elementului i
// in a[i][j] retin profitul maxim obtinut dintr-o submultime de i elemente cu greutate j
int main()
{
	freopen ("rucsac.in", "r", stdin);
	scanf("%d%d", &n, &g);
	int i;
	for(i=1; i<=n; i++)
		scanf("%hd%hd", &W[i], &P[i]);
	int j;
	for(i=1; i<=n; i++)
	{
		for(j=0; j<=g; j++)
		{
			a[1][j] = a[0][j];
			if (W[i] <= j)
				a[1][j] = max(a[1][j], a[0][j-W[i]] + P[i]);
		}
		for(j=0; j<=g; j++)
			a[0][j] = a[1][j];
	}
	
	freopen ("rucsac.out", "w", stdout);
	int x;
	x=a[1][g];
	printf("%d\n", x);
	
	return 0;
}