#include <cstdio>

struct {long g; long val;} b[10001], a[5001];

long i, j, max, N, G;

inline int maxim(long x, long y) {
	return (x>y)?x:y;
}

int main() {
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	
		scanf("%ld %ld", &N, &G);
		
		for (i = 1; i <= N; ++i) {
			scanf("%ld %ld", &a[i].g, &a[i].val);
		}
		
		for (i = 1; i <= N; ++i) {
			b[a[i].g].val = maxim(b[a[i].g].val, a[i].val);
			b[a[i].g].g = i;
			j = 1;
			while (j + a[i].g <= G && j <= G) {
				if (b[j].g != i) {
					b[j+a[i].g].val = maxim(b[j+a[i].g].val, b[j].val + a[i].val);
					b[j+a[i].g].g = i;
					if (b[j+a[i].g].val > max) {
						max = b[j+a[i].g].val;
					}
				}
			}
		}
		
		printf("%ld\n", max);
	
	return 0;
}