#include<iostream>
#include<algorithm>

using namespace std;

#define nMAX 100 
#define vMAX 1000
#define WMAX 100

int main(){

	int n,W;
	int v[nMAX+1],w[nMAX+1];
	int dp[nMAX+1][WMAX+1];

	cin>>n>>W;
	for(int i=0;i<n;i++){
		cin>>v[i]>>w[i];
	}

	for(int i=0;i<=W;i++) dp[0][i]=0;

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