#include <iostream>
#include <algorithm>
#include "stdio.h"

int  dp[2][10010];
int main() {
	freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
	int w[5001], p[5001], N, G;
	scanf("%d %d", &N, &G);
	for(int i = 1; i <= N;i++){
		scanf("%d %d", w + i,p + i);
	}
	int line = 0;
	for(int i = 1; i <= N;i++, line = 1 - line){
		for(int j = 0; j <= G;j++){
			dp[1-line][j] = dp[line][j];
			if(w[i] <= j)
				dp[1 - line][j] = std::max(dp[1 - line][j], dp[line][j-w[i]] + p[i]);
		}
	}
	printf("%d", dp[line][G]);
	return 0;
}