#include<bits/stdc++.h>
using namespace std;

long long int N,G,w[10001],p[10001],dp[2][10001],ans;
int main(){
	ifstream cin("rucsac.in");	
	ofstream cout("rucsac.out");
	cin >> N >> G;
	int linie=1;
	for (int i=1; i<=N; i++) {
		cin >> w[i] >> p[i];
	}
	for (int i=1; i<=N; i++) {
		for (int j=1; j<=G; j++) {
				if (j >= w[i]) {
				dp[linie][j] = max(dp[!linie][j-w[i]]+p[i], dp[!linie][j]);
				ans=dp[linie][j];
				}
				else {
				dp[linie][j] = dp[!linie][j];
				ans=dp[linie][j];
				}
		}
		linie=!linie;
	}
	cout << ans;
	}