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

//dp[N][W] - profitul maxim pt o submultime a primelor N elemente ce are greutatea maxim W
//dp[N][W] = max(dp[N-1][W],dp[N-1][W-w[N]]+w[N])

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int main() {
	int n, g;
	cin >> n >> g;
	int w[n+1], p[n+1], dp[2][g+1];
	for(int i=1;i<=n;i++) 
		cin >> w[i] >> p[i];
	for(int i=0;i<=g;i++)
		dp[0][i] = 0;
	for(int i=1;i<=n;i++) {
		dp[1][0] = 0;
		for(int j=1;j<=g;j++) {
			dp[1][j] = dp[0][j];
			if(j>=w[i])
				dp[1][j] = max(dp[1][j], dp[0][j-w[i]]+p[i]);
		}
		for(int j=0;j<=g;j++)
			dp[0][j] = dp[1][j];
	}
	cout << dp[0][g];
	return 0;
}