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


int main(){
	int n,w1;
	while(cin>>n>>w1){
		int w[n]={0};
		int v[n]={0};
		for(int i=0;i<n;i++){
			cin>>w[i];
			cin>>v[i];
		}
		int dp[n+1][w1+1]={0};
		for(int i=1;i<=n;i++){
			for(int j=1;j<=w1;j++){
				if(j-w[i-1]>=0){
					dp[i][j]=max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);
				}
				else dp[i][j]=dp[i-1][j];
			}
		}
		cout<<dp[n][w1];
		cout<<endl;
	}
}