#include <stdio.h>

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

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

	
	for (int i=1; i<=N; ++i){
		for (int j=0; j<=G; ++j){
			dp[i][j] = dp[i-1][j];

			if (w[i] <= j)
				dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+p[i]);
		}

	}
	printf("%d", dp[N][G]);


	return 0;
}