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

using namespace std;

int w[5003],v[5003],dp[5003][10003];
	
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=0;i<=g;i++)dp[0][i]=0;
	
	for(int i=1;i<=n;i++)
	for(int j=0;j<=g;j++)if(w[i]>j)dp[i][j]=dp[i-1][j];
	else dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);
	
	/*for(int i=0;i<=n;i++){
	for(int j=0;j<=g;j++)cout<<dp[i][j]<<' ';
	cout<<'\n';
    }*/
    
	cout<<dp[n][g];
}