#include <stdio.h>

int max(int a, int b){
	if (a>b)
		return a;
	return b;
}
int dp[2][5011];
int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int N, G;
	scanf("%d %d", &N, &G);

	int w[5011], p[5011];
	for (int i=1; i<=N; ++i)
		scanf("%d %d", &w[i], &p[i]);

	int l=0;
	for (int i=1; i<=N; ++i){
		l=1-l;
		for (int j=0; j<=G; ++j){
			dp[1-l][j] = dp[l][j];
			if (w[i] <= j)
				dp[1-l][j] = max(dp[1-l][j], dp[l][j-w[i]]+p[i]);
		}

	}
	printf("%d\n", dp[1-l][G]);


	return 0;
}