#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void) {
	FILE *fin, *fout;
	int n, v[3][10005], g[6001], val[6001], gmax, i, j, h, v1, v2;
	fin = fopen("rucsac.in", "r");
	fout = fopen("rucsac.out", "w");
	memset(v, 0, sizeof(v));
	fscanf(fin, "%d %d", &n, &gmax);
	for (i = 1; i <= n; i++)
		fscanf(fin, "%d %d", &g[i], &val[i]);
	for (j = 1; j <= gmax; j++)
		if (j < g[1])
			v[1][j] = 0;
		else {
			v2 = val[1];
			v[1][j] = v2;
		}
	for (i = 2; i <= n; i++){
		for (j = 1; j <= gmax; j++)
			if (j < g[i])
				v[2][j] = v[1][j];
			else {
				v1 = v[1][j];
				v2 = val[i] + v[1][j - g[i]];
				if (v1 > v2)
					v[2][j] = v1;
				else
					v[2][j] = v2;
			}
		for (h = 1; h <= gmax; h++)
			v[1][h] = v[2][h];
	}
	fprintf(fout, "%d", v[2][gmax]);
	fclose(fin);
	fclose(fout);
	return 0;
}