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

using namespace std;


long long int w[5003],v[5003],dp[2][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++)if(i%2==1){
	for(int j=0;j<=g;j++)
			if(w[i]>j)dp[1][j]=dp[0][j];
	     else dp[1][j]=max(dp[0][j],v[i]+dp[0][j-w[i]]);
	}
	else {
		for(int j=0;j<=g;j++)
		if(w[i]>j)dp[0][j]=dp[1][j];
	     else dp[0][j]=max(dp[1][j],v[i]+dp[1][j-w[i]]);
	}
	cout<<max(dp[1][g],dp[0][g]);
}