#include <stdio.h>
#define MAX 10005
#define max(a, b) (a > b ? a : b)

typedef struct{
	int w, p;
} ruc;

int n, g, i, j;
long long d[2][MAX];
ruc v[MAX];

void rucsac();

int main(){
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	scanf("%d%d", &n, &g);
	for(i = 0; i < n; i++)
		scanf("%d%d", &v[i].w, &v[i].p);

	rucsac();
	printf("%lld\n", d[(n - 1) & 1][g]);
	return 0;
}

void rucsac(){
	for(i = v[0].w; i <= g; i++)
		d[0][i] = v[0].p;

	for(i = 1; i < n; i++)
		for(j = 0; j <= g; j++)
			if(j - v[i].w < 0)
				d[i & 1][j] = d[(i - 1) & 1][j];
			else
				d[i & 1][j] = max(d[(i - 1) & 1][j], d[(i - 1) & 1][j - v[i].w] + v[i].p);
}