#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;


long long int w[5003],v[5003],dp[5003];	

int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int n, g;
	cin>>n>>g;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	
	for(int i=1;i<=n;i++)
	for(int j=g;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	
	
	cout<<dp[g];
}