#include<fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,G;
short g[5005],p[5005];
int dp[2][10005];
int main(){
	cin >> n >>G;
	for (int i = 1; i <= n; i++){
		cin >> g[i] >> p[i];
	}
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= G; j++){
			dp[0][j] = dp[1][j];
			if (j - g[i] >= 0){
				dp[1][j] = max (dp[0][j], (dp[0][j-g[i]] + p[i]));
			}
		}
		for (int j = 0; j <= G; j++){
			dp[0][j] = dp[1][j];
		}
	}
	cout << dp[1][G];
}