#include<stdio.h>
#define D 1010
void nappu(void);
int C, N, x, c[D], v[D], i, j, Cx[D][D], capacity[D][D];

int main(void) {

	/*
	 printf("????????????????????????????????\?????????????????????:");
	 scanf("%d", &C);
	 printf("??????????¨?????????\?????????????????????:");
	 scanf("%d", &N);
	 for (j = 1; j <= N; j++) {
	 printf("?????????????????¨???????????\?????????????????????:");
	 scanf("%d %d", &c[j], &v[j]);

	 }
	 */
	scanf("%d %d", &N, &C);
	for (j = 1; j <= N; j++) {
		scanf("%d %d", &v[j], &c[j]);
	}
	nappu();
return 0;
}

void nappu(void) {
	for (j = 0; j <= N; j++) {
		for (i = 0; i <= C; i++) {
			if (j == 0) {
				Cx[i][j] = 0;
			} else {
				if (capacity[i - c[j]][j - 1] + c[j] <= i
						&& Cx[i - c[j]][j - 1] + v[j] > Cx[i][j - 1]) {
					Cx[i][j] = Cx[i - c[j]][j - 1] + v[j];
					capacity[i][j] = capacity[i - c[j]][j - 1] + c[j];
				} else if (c[j] <= i && c[j] == capacity[i][j - 1]) {
					if (v[j] > v[j - 1]) {
						Cx[i][j] = v[j];
						capacity[i][j] = c[j];
					} else {
						Cx[i][j] = v[j - 1];
						capacity[i][j] = capacity[i][j - 1];
					}
				} else {
					Cx[i][j] = Cx[i][j - 1];
					capacity[i][j] = capacity[i][j - 1];
				}
			}
			//printf("%d ", Cx[i][j]);
		}
		//puts("");
	}
	//printf("??????%d??????????????????????????\???????????????????????????????????§???%d\n", C, Cx[C][N]);
	printf("%d\n", Cx[C][N]);
}