#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
#define MIN (1e-10)
#define equal(a,b) (abs((a)-(b))<MIN)
#define v2 ten
#define chokusen senbun
#define tenten senbun
#define takaku vec<ten>
using namespace std;
void solve();

struct pea {
	ll f, s;
	bool operator<(const pea &p)const {
		return f != p.f ? f < p.f : s < p.s;
	};
};
struct tri {
	ll f, s, t;
	bool operator<(const tri &p)const {
		if (f != p.f)return f < p.f;
		if (s != p.s)return s < p.s;
		return t < p.t;
	};
};
class ten {
public:
	ld x, y;

	ten operator+(ten p) { return { x + p.x,y + p.y }; }
	ten operator-(ten p) { return { x - p.x,y - p.y }; }
	ten operator*(ld k) { return { k*x,k*y }; }
	ten operator/(ld k) { return { x / k,y / k }; }

	ld abs() { return sqrt(abs2()); }
	ld abs2() { return x * x + y * y; };

	bool operator<(const ten &p)const { return x != p.x ? x < p.x : y < p.y; };
	bool operator==(const ten &p)const {
		return (-MIN < x - p.x) && (x - p.x < MIN) && (-MIN < y - p.y) && (y - p.y < MIN);
	};

	ld naiseki(v2 b) { return x*b.x + y*b.y; }
	ld gaiseki(v2 b) { return x*b.y - y*b.x; }
};
struct senbun { ten p1, p2; };
struct en { ten o; ld r; };

//互いに素な集合
class ufset {
public:
	vll rank, p;
	ufset(ll n) {
		rank.resize(n, 0);
		p.resize(n, 0);
		rep(i, 0, n)make(i);
	}
	void reset(ll n) {
		rank.resize(n, 0);
		p.resize(n, 0);
		rep(i, 0, n)make(i);
	}
	void make(ll i) {
		p[i] = i;
		rank[i] = 0;
	}
	bool same(ll i, ll j) { return find(i) == find(j); }
	void unite(ll i, ll j) { link(find(i), find(j)); }
	void link(ll i, ll j) {
		if (rank[i] > rank[j])p[j] = i;
		else {
			p[i] = j;
			if (rank[i] == rank[j])rank[j]++;
		}
	}
	ll find(ll i) {
		if (p[i] != i)p[i] = find(p[i]);
		return p[i];
	}
};

//nCk(mod p)
class nck {
public:
	ll NUM, p;
	vll fac, finv, inv;
	nck(ll maxn, ll mod = MOD) {
		NUM = maxn + 1;
		p = mod;
		fac.resize(NUM);
		finv.resize(NUM);
		inv.resize(NUM);
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		rep(i, 2, NUM) {
			fac[i] = fac[i - 1] * i%p;
			inv[i] = p - inv[p%i] * (p / i) % p;
			finv[i] = finv[i - 1] * inv[i] % p;
		}
	}
	ll c(ll n, ll k) { return fac[n] * (finv[k] * finv[n - k] % p) % p; }
};

//最大公約数
ll gcd(ll n, ll m) {
	ll k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return m;
}
ll gcd(vector<ll> a) {
	rep(i, 1, a.size()) {
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
	}
	return a.back();
}

//最小公倍数
ll lcm(ll n, ll m) {
	ll t = n * m, k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return t / m;
}
ll lcm(vector<ll> a) {
	ll n;
	rep(i, 1, a.size()) {
		n = a[i - 1] * a[i];
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
		n /= a[i];
		a[i] = n;
	}
	return n;
}

//a^b(mod p)
ll pow2(ll a, ll b, ll p = MOD) {
	if (b == -1)return pow2(a, p - 2);
	ll res = 1;
	if (b > 0) {
		res = pow2(a, b / 2);
		if (b % 2 == 0)res = res * res%p;
		else res = res * res%p*a%p;
	}
	return res;
}

//トポロジカルソート
void tsort(const vec<vll> &c, vll &a) {
	ll n = c.size();
	vll p(n, 0);
	rep(i, 0, n)rep(j, 0, c[i].size())p[c[i][j]]++;
	rep(i, 0, n)if (p[i] == 0) {
		deque<ll> d; d.pub(i);
		while (!d.empty()) {
			ll j = d.front(); d.pof();
			a.pub(j);
			rep(k, 0, c[j].size()) {
				ll l = c[j][k];
				p[l]--;
				if (p[l] == 0) {
					p[l] = -1;
					d.pub(l);
				}
			}
		}
	}
}

//深さ優先探索
vec<bool> seen;
void dfs(const vec<vll> &c, ll i = 0) {
	seen[i] = true;
	rep(j, 0, c[i].size()) {
		if (!seen[c[i][j]])dfs(c, c[i][j]);
	}
}

//最小全域木
ll kruskal(ll v, vec<tri> &e) {
	ll sum = 0;
	sort(ALL(e));
	ufset s(v);
	rep(i, 0, e.size()) {
		if (!s.same(e[i].s, e[i].t)) {
			s.unite(e[i].s, e[i].t);
			sum += e[i].f;
		}
	}
	return sum;
}

//単一始点最短経路
void dijkstra(const vec<vec<pea>> &c, ll v, vll &d) {
	d[v] = 0;
	ll n = c.size();
	ll count = 1;
	vec<bool> seen(n, false);
	seen[v] = true;
	yuque<pea> hen;
	rep(i, 0, c[v].size())hen.push({ -c[v][i].f,c[v][i].s });
	while (count != n) {
		if (hen.empty())break;
		pea k = hen.top(); hen.pop();
		while (seen[k.s]) {
			if (hen.empty()) {
				count = -1;
				break;
			}
			k = hen.top();
			hen.pop();
		}
		if (count == -1)break;
		d[k.s] = -k.f;
		count++;
		seen[k.s] = true;
		rep(i, 0, c[k.s].size())hen.push({ k.f - c[k.s][i].f,c[k.s][i].s });
	}
}

//全点対間最短経路
bool floyd(vec<vll> &d) {
	ll n = d.size();
	rep(i, 0, n)d[i][i] = 0;
	rep(k, 0, n) {
		rep(i, 0, n) {
			if (d[i][k] != MOD) {
				rep(j, 0, n) {
					if (d[k][j] != MOD) {
						d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
					}
				}
			}
		}
	}
	bool b = true;
	rep(i, 0, n)if (d[i][i] < 0)b = false;
	return b;
}

//計算幾何学
v2 beku(ld r,ld t){
	return { r*cos(t),r*sin(t) };
}
ld kakudo(v2 a) {
	return atan2(a.y, a.x);
}
ten shaei(ten p, chokusen l) {
	v2 a = l.p2 - l.p1;
	return l.p1 + a * a.naiseki(p - l.p1) / a.abs2();
}
ten hansha(ten p, chokusen l) {
	return shaei(p, l) * 2 - p;
}
ld tenchoku(ten p, chokusen l) {
	v2 a = l.p2 - l.p1;
	return abs(a.gaiseki(p - l.p1)) / a.abs();
}
ld tensen(ten p, senbun s) {
	if ((p - s.p1).naiseki(s.p2 - s.p1) < 0)return (p - s.p1).abs();
	if ((p - s.p2).naiseki(s.p1 - s.p2) < 0)return (p - s.p2).abs();
	return tenchoku(p, s);
}
ll ccw(ten p0, ten p1, ten p2) {
	v2 a = p1 - p0, b = p2 - p0;
	if (a.gaiseki(b) > MIN)return -1;//012反時計回り
	if (a.gaiseki(b) < -MIN)return 1;//012時計回り
	if (a.naiseki(b) < -MIN)return -2;//102
	if (a.abs2() < b.abs2())return 2;//012
	return 0;//021
}
bool majiwaru(senbun s, senbun t) { 
	return ccw(s.p1, s.p2, t.p1)*ccw(s.p1, s.p2, t.p2) <= 0 
		&& ccw(t.p1, t.p2, s.p1)*ccw(t.p1, t.p2, s.p2) <= 0; 
}
ld sensen(senbun s, senbun t) {
	if (majiwaru(s, t))return 0;
	return min({ tensen(s.p1,t),tensen(s.p2,t),tensen(t.p1,s),tensen(t.p2,s) });
}
ten koten(senbun s, senbun t) {
	v2 a = t.p2 - t.p1;
	ld d1 = abs(a.gaiseki(s.p1 - t.p1));
	ld d2 = abs(a.gaiseki(s.p2 - t.p1));
	return s.p1 + (s.p2 - s.p1)*d1 / (d1 + d2);
}
tenten koten(en c, chokusen l) {
	ten h = shaei(c.o, l);
	ld k = sqrt(c.r*c.r - (h - c.o).abs2());
	v2 a = (l.p1 - l.p2) / (l.p1 - l.p2).abs();
	return { h + a * k,h - a * k };
}
tenten koten(en c1, en c2) {
	ld d = (c2.o - c1.o).abs();
	ld s = acos((c1.r*c1.r + d * d - c2.r*c2.r) / (2 * c1.r*d));
	ld t = kakudo(c2.o - c1.o);
	return { c1.o + beku(c1.r,t + s),c1.o + beku(c1.r,t - s) };
}
ll uchi(ten p, takaku &g) {
	//2:IN,1:ON,0:OUT
	ll n = g.size();
	v2 a, b;
	bool x = false;
	rep(i, 0, n) {
		a = g[i] - p; b = g[(i + 1) % n] - p;
		if (abs(a.gaiseki(b)) < MIN&&a.naiseki(b) < MIN)return 1;
		if (a.y > b.y)swap(a, b);
		if (a.y < MIN&&MIN<b.y&&a.gaiseki(b)>MIN)x = !x;
	}
	return x ? 2 : 0;
}

//凸包
takaku andrew(takaku g) {
	takaku u, b;
	if (g.size() < 3)return g;
	sort(ALL(g));
	u.pub(g[0]); u.pub(g[1]);
	b.pub(g.back()); b.pub(g[g.size() - 2]);
	rep(i, 2, g.size()) {
		rrep(j, u.size(), 2) {
			if (ccw(u[j - 2], u[j - 1], g[i]) == 1)break;
			u.pob();
		}
		u.pub(g[i]);
	}
	rrep(i, g.size() - 3, 0) {
		rrep(j, b.size(), 2) {
			if (ccw(b[j - 2], b[j - 1], g[i]) == 1)break;
			b.pob();
		}
		b.pub(g[i]);
	}
	rep(i, 1, b.size() - 1)u.pub(b[i]);
	return u;
}

//線分交差問題
ll kotensu(vec<senbun> s) {
	ll n = s.size();
	struct endp {
		ten p; ll id, kind;//kind => 0:BOTTOM,1:LEFT,2:RIGHT,3:TOP
		bool operator<(const endp &e)const {
			return p.y != e.p.y ? p.y < e.p.y : kind < e.kind;
		};
	};
	
	vec<endp> ep(2 * n);
	rep(i, 0, n) {
		if (equal(s[i].p1.y, s[i].p2.y)) {
			if (s[i].p1.x > s[i].p2.x)swap(s[i].p1, s[i].p2);
			ep[2 * i] = { s[i].p1,i,1 };
			ep[2 * i + 1] = { s[i].p2,i,2 };
		}
		else {
			if (s[i].p1.y > s[i].p2.y)swap(s[i].p1, s[i].p2);
			ep[2 * i] = { s[i].p1,i,0 };
			ep[2 * i + 1] = { s[i].p2,i,3 };
		}
	}

	sort(ALL(ep));

	set<ll> bt;
	ll cnt = 0;
	rep(i, 0, 2 * n) {
		if (ep[i].kind == 3)bt.erase(ep[i].p.x);
		else if (ep[i].kind == 0)bt.insert(ep[i].p.x);
		else if (ep[i].kind == 1)cnt += distance(bt.lob(s[ep[i].id].p1.x), bt.upb(s[ep[i].id].p2.x));
	}
	return cnt;
}

//0-1 ナップザック問題
ll maxvalue(ll W, const vll &v, const vll &w, vll &select) {
	ll n = v.size();

	vec<vll> dp(n + 1, vll(W + 1, 0));
	vec<vec<bool>> tuika(n + 1, vec<bool>(W + 1, false));

	rep(i, 1, n + 1) {
		rep(j, 1, W + 1) {
			if (j - w[i - 1] >= 0 && dp[i - 1][j - w[i - 1]] + v[i - 1] > dp[i - 1][j]) {
				dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1];
				tuika[i][j] = true;
			}
			else dp[i][j] = dp[i - 1][j];
		}
	}

	ll ww = W; select.clear();
	rrep(i, n, 1) {
		if (tuika[i][ww]) {
			select.pub(i - 1);
			ww -= w[i - 1];
		}
	}
	reverse(ALL(select));

	return dp[n][W];
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed;
	solve();
}
void solve() {
	ll n, W; cin >> n >> W;
	vll v(n), w(n);
	rep(i, 0, n)cin >> v[i] >> w[i];
	vll dp(W + 1, 0);
	rep(i, 1, W + 1) {
		rep(j, 0, n) {
			if (i - w[j] >= 0)dp[i] = max(dp[i], dp[i - w[j]] + v[j]);
		}
	}
	cout << dp[W] << kai;
}


Measured memory_bytes: 3280