#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int  n, G, p[5000], g[5000], d[5000][5000];

int main(){

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

			if (g[i] <= j && (d[i - 1][j - g[i]] + p[i] > d[i - 1][j])){
				d[i][j] = d[i - 1][j - g[i]] + p[i];
			}
			else d[i][j] = d[i - 1][j];

		}

	printf("%d", d[n][G]);
	return 0;
}