// chenkl1995@gmail.com
// https://atcoder.jp/contests/dp/tasks
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T> inline void IN(T &x) {
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
	x *= f;
}
template<typename A, typename B> inline void IN(A &x, B &y) { IN(x); IN(y); }
template<typename A, typename B, typename C> inline void IN(A &x, B &y, C &z) { IN(x); IN(y); IN(z); }

#define FastI ios_base::sync_with_stdio(0), cin.tie(0);
#define FastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define endl '\n'
#define REP(i, l, r) for (auto i = (l); i <= (r); ++i)
#define PER(i, l, r) for (auto i = (l); i >= (r); --i)
#define FOR(i, l, r) for (auto i = (l); i < (r); ++i)
#define ROF(i, l, r) for (auto i = (l); i > (r); --i)
#define FORN(i, n) for (auto i = 0; i < (n); ++i)
#define REPN(i, n) for (auto i = 1; i <= (n); ++i)
#define FORA(i, a) for (auto &i : a)
template<class T> void cout_1d(T &v) { FORA(i, v) cout << i << " "; puts(""); }
template<class T> void cout_2d(T &vv) { FORA(v, vv) cout_1d(v); }
#define ALL(X) (X).begin(), (X).end()
#define RALL(X) (X).rbegin(), (X).rend()
#define SIZE(X) ((int)(X).size())
#define UNIQUE(x) (X).erase(unique(ALL(x), (X).end())
#define ZERO(a) memset(a, 0, sizeof(a))
#define NEG1(a) memset(a, -1, sizeof(a))
#define MAXA(a) memset(a, 0x3f, sizeof(a))
#define MAXB(b) memset(b, 0x7f, sizeof(b))
#define MP make_pair
#define PB push_back
#define X first
#define Y second

const LD PI = acos(-1.0);
const LL MOD = 998244353;
//const LL MOD = 1e9+7;
const LL MAXN = 2e5 + 7;

int h[MAXN];
void solve1() {
	int N;  IN(N);
	REPN(i, N) IN(h[i]);
	// VI dp(N+1, 0);  dp[2] = abs(h[2] - h[1]);
	// REP(i, 3, N) dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
	VI dp(N+1, 0);
	REP(i, 2, N) dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), 
			i <= 2 ? INT_MAX : dp[i-2] + abs(h[i] - h[i-2]));
	cout << dp[N] << endl;
}

void solve2() {
	int N, K;  IN(N, K);
	REPN(i, N) IN(h[i]);
	VI dp(N+1, INT_MAX);
	dp[1] = 0;
	REP(i, 2, N) REP(j, 1, K) // if (j >= i) break;
		dp[i] = min(dp[i], i <= j ? INT_MAX : dp[i-j] + abs(h[i] - h[i-j]));
	cout << dp[N] << endl;
}

// int a[MAXN], b[MAXN], c[MAXN];
int v3[MAXN][3];
void solve_Vacation() {
	// int N;  IN(N);
	// int mxa, mxb, mxc;
	// REPN(i, N) IN(a[i], b[i], c[i]);
	// mxa = a[1];  mxb = b[1];  mxc = c[1];
	// REP(i, 2, N) {
	//     int ta = mxa, tb = mxb, tc = mxc;
	//     mxa = a[i] + max(tb, tc);
	//     mxb = b[i] + max(ta, tc);
	//     mxc = c[i] + max(ta, tb);
	// }
	// cout << max(mxa, max(mxb, mxc)) << endl;
	int N;  IN(N);
	FORN(i, N) FORN(j, 3) IN(v3[i][j]);
	VI mx(v3[0], v3[0]+3);
	FOR(i, 1, N) {
		VI t = mx;
		FORN(j, 3)
			mx[j] = v3[i][j] + max(t[(j+1)%3], t[(j+2)%3]);
	}
	cout << *max_element(ALL(mx)) << endl;
}

LL w[MAXN], v[MAXN];
void solve_Knapsack_1() {
	int N, W;  IN(N, W);
	REPN(i, N) IN(w[i], v[i]);
	VV<LL> dp(N+1, V<LL>(W+1, 0));
	REPN(i, N) REPN(j, W)
		dp[i][j] = (j < w[i]) ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
	cout << dp[N][W] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    // FastI

	// solve1();
	// solve2();
	// solve_Vacation();
	solve_Knapsack_1();

    return 0;
}


Measured memory_bytes: 80256