#include<bits/stdc++.h>

using namespace std;

int n,G;
int dp[3][10010];
bool u;

int c[5010], m[5010];

int main() {
	ifstream cin("rucsac.in");
	fstream cout("rucsac.out");
	
	cin>>n>>G;
	
	for (int i=1; i<=n; i++) cin>>m[i]>>c[i];
	
	u=0;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=G; j++) {
			if (m[i]<=j) dp[u][j] = max(dp[!u][j], dp[!u][j-m[i]] + c[i]);
			else dp[u][j] = dp[!u][j];
		}
		u=!u;
	}
	cout<<dp[!u][G];
	
	
	return 0;
}