//https://atcoder.jp/contests/dp/tasks/dp_d

#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


using namespace std;

typedef long long int ll;

const int precision = 16;
const int modulo =  1000000007; // 10^9 + 7
using ll = long long;
const double EPS = 1e-9;


// ll recKS1(int ind, const vector<int> & w, const vector<int> & c, int W) 
// {
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;

// 	if(w[ind] > W) {
// 		return recKS1(ind + 1, w, c, W);
// 	}

// 	auto r1 = c[ind] + recKS1(ind + 1, w, c, W - w[ind]);
// 	auto r2 = recKS1(ind + 1, w, c, W);
// 	return max(r1, r2);
// }

// auto h = std::hash<ll>();
// auto _hash = [&h](pair<int, int> p) ->ll {
// 	return h((ll)p.first | ((ll)p.second << 32));
// };



// ll recKS2(int ind, const vector<int> & w, const vector<int> & c, int W, gp_hash_table<pair<int, int>, ll,decltype(_hash)>  & memo) 
// {
// 	if(memo.find({ind, W}) != memo.end()) return memo[{ind, W}];
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;
	
// 	if(w[ind] > W) {
// 		auto ret = recKS2(ind + 1, w, c, W, memo);
// 		memo[{ind, W}] = ret;
// 		return memo[{ind, W}];
// 	}

// 	auto r1 = c[ind] + recKS2(ind + 1, w, c, W - w[ind], memo);
// 	auto r2 = recKS2(ind + 1, w, c, W, memo);
// 	auto r = max(r1, r2);
// 	memo[{ind, W}]  = r;
// 	return r;
// }

// ll recKS3(int ind, const vector<int> & w, const vector<int> & c, int W, vector<vector<ll>> & memo) 
// {
// 	if(memo[ind][W] != -1) return memo[ind][W];
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;
	
// 	if(w[ind] > W) {
// 		auto ret = recKS3(ind + 1, w, c, W, memo);
// 		memo[ind][W] = ret;
// 		return memo[ind][W];
// 	}

// 	auto r1 = c[ind] + recKS3(ind + 1, w, c, W - w[ind], memo);
// 	auto r2 = recKS3(ind + 1, w, c, W, memo);
// 	auto r = max(r1, r2);
// 	memo[ind][W]  = r;
// 	return r;
// }


// ll itKS4(const vector<int> & wA, const vector<int> & c, int C) 
// {
// 	int n = wA.size();

// 	vector<vector<ll>> dp(n + 1, vector<ll> (C + 1, 0));

// 	for(auto i = 1; i <= n; ++i) {
// 		for(auto w = 1; w <= C; ++w) {
// 			if(wA[i - 1]  <= w) {
// 				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wA[i - 1]] + c[i - 1]);
// 			} else {
// 				dp[i][w] = dp[i - 1][w];
// 			}
// 		}
// 	}

// 	return dp[n][C];
// }

ll itKS5(const vector<int> & wA, const vector<int> & c, int C) 
{
	int n = wA.size();

	vector<ll> dp(C + 1, 0), dp1(C + 1, 0);

	for(auto i = 1; i <= n; ++i) {
		for(auto w = wA[i - 1]; w <= C; ++w) {
			dp[w] = max( dp1[w] , dp1[w - wA[i - 1]] + c[i - 1]);

		}
		dp1 = dp;
		// for(auto it : dp) cout << it << " " ;
		// cout <<endl;
	}
	return dp[C];
}

void solveKS1()
{
	int n, W; cin >> n >> W;
	vector<int> w(n), c(n);
	for(auto i = 0; i < n; ++i) {
		cin >> w[i] >> c[i];
	}

	//auto ret = recKS1(0, w, c, W);

	// gp_hash_table<pair<int, int>, ll, decltype(_hash)> memo(_hash);
	// auto ret = recKS2(0, w, c, W, memo);

	// vector<vector<ll>> memo(n + 1, vector<ll> (W + 1, -1));
	// auto ret = recKS3(0, w, c, W, memo);

	//auto ret = itKS4(w, c, W);
	auto ret = itKS5(w, c, W);
	cout << ret <<endl;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(precision);
	cout.setf(ios_base::fixed);

	solveKS1();
	return 0;
}



Measured memory_bytes: 1792