//============================================================================
// Name        : dpl_1b.cpp
// Author      : afterCmidday
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, W, v[100], w[100], dp[10001];
	cin >> n >> W;
	for(int i = 0;i < n;i++){
		cin >> v[i] >> w[i];
	}
	fill(dp,dp + 10001,-1);
	dp[0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = W;j >= 0;j--){
			if(j - w[i] >= 0 && dp[j - w[i]] != -1 && (dp[j] == -1 || dp[j] < dp[j - w[i]] + v[i])){
				dp[j] = dp[j - w[i]] + v[i];
			}
		}
	}
	int ans = 0;
	for(int i = 0;i <= W;i++){
		ans = max(ans,dp[i]);
	}
	cout << ans << endl;
	return 0;
}