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

long long int N,G,w[10001],p[10001],dp[10001][5001],ans;
int main(){
	ifstream cin("rucsac.in");	
	ofstream cout("rucsac.out");
	cin >> N >> G;
	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[i][j] = max(dp[i-1][j-w[i]]+p[i], dp[i-1][j]);
				ans=dp[i][j];
				}
				else {
				dp[i][j] = dp[i-1][j];
				ans=dp[i][j];
				}
		}
	}
	cout << ans;
	}