#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#include<cmath>
#include<queue>
#include<stack>
#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}
using namespace std;
typedef long long ll;
ll gcd(ll, ll);
vector<bool> to_binary(int);
int sum(vector<int>);
int min(vector<int>);
int max(vector<int>);
ll nCr(ll n, ll r);

const ll INF = 1LL << 60;

typedef tuple<ll, ll> mtupl;

bool mycomp(mtupl x, mtupl y) {
	return get<1>(x) < get<1>(y);
}

vector<vector<ll>> memo;

ll get(int x, int y) {
	if (memo[x][y] != -1)
		return memo[x][y];

	if (x == 0) return 1;
	if (y < x) return 0;

	memo[x][y] = get(x, y - 1) + get(x - 1, y - 1);
	return memo[x][y];
}

ll mpow(ll a, ll b) {
	ll ans = 1;
	for (ll i = 0; i < b; i++) {
		ans *= a;
		ans %= 1000000007;
	}
	return ans;
}

ll nCr(ll n, ll r) {
	ll res = 1;
	for (int i = 0; i < r; i++) {
		res *= (n - i);
	}
	for (int i = 1; i <= r; i++) {
		res /= i;
	}
	return res;
}

int vsum(vector<int> v) {
	int res = 0;
	for (auto it = v.begin(); it != v.end(); it++)
		res += *it;
	return res;
}
int vmin(vector<int> v) {
	int min = INT32_MAX;
	for (auto it = v.begin(); it != v.end(); it++)
		min = std::min(min, *it);
	return min;
}
int vmax(vector<int> v) {
	int max = INT32_MIN;
	for (auto it = v.begin(); it != v.end(); it++)
		max = std::max(max, *it);
	return max;
}

ll gcd(ll A, ll B) {
	if (A == 0 || B == 0) return max(A, B);
	int r = A % B;
	while (r != 0) {
		A = B;
		B = r;
		r = A % B;
	}
	return B;
}

ll _gcd(ll A, ll B) {
	return (B == 0) ? A : gcd(A % B, B);
}

vector<bool> to_binary(int x) {
	vector<bool> res;
	while (x != 0) {
		res.push_back(x % 2);
		x /= 2;
	}
	return res;
}

template<int index>
bool comp(tuple<ll, ll, ll, ll> a, tuple<ll, ll, ll, ll> b) {
	return get<index>(a) < get<index>(b);
}

int vector_finder(std::vector<ll> vec, ll number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return index;
	}
	else { // 発見できなかったとき
		return 0;
	}
}


int len(int x) {
	return (int)log10(x) + 1;
}

int same_vec(vector<int> a, vector<int> b) {
	int res = 1, num = a.size();
	for (int i = 0; i < num; i++) {
		if (a[i] != b[i]) {
			res = 0;
			break;
		}
	}
	return res;
}


ll fibs[100] = { 0 };
ll fib(int n) {
	if (fibs[n] == 0) {
		return fibs[n] = fib(n - 1) + fib(n - 2);
	}
	return fibs[n];
}


ll dp[110][100100] = { 0 };

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Program Start	

	int N, W;
	cin >> N >> W;
	vector<int> w(N), v(N);

	rep(i, N) cin >> w[i] >> v[i];

	for (int i = 0; i < N; i++) {
		for (int sum_w = 0; sum_w <= W; sum_w++) {
			if (sum_w - w[i] >= 0) {
				dp[i + 1][sum_w] = max(
					dp[i + 1][sum_w],
					dp[i][sum_w - w[i]] + v[i]
				);
			}
			dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]);
		}
	}

	cout << dp[N][W] << endl;

ProgramEndPointLabel:;

	//Program End
#ifndef DEBUG
	system("pause");
#endif // !DEBUG


	return 0;
}




Measured memory_bytes: 79608