#include <cstdio>
#include <algorithm>
using namespace std;

int dp[3][10010], w[5011], p[5011];

int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int N, G;
	scanf("%d %d", &N, &G);

	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[l][G]);


	return 0;
}