#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define int long long
using namespace std;
const int Nmax = 1e4 + 5;
const int mod = 1e9 + 7;

struct obiect{
	int w, val;
};

obiect arr[Nmax];
int dp[2][Nmax];

signed main() {
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, w; cin >> n >> w;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i].w >> arr[i].val;
	}
	int cr = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (j - arr[i].w >= 0) {
				dp[cr][j] = max(dp[1 - cr][j], dp[1 - cr][j - arr[i].w] + arr[i].val);
			}
			else {
				dp[cr][j] = dp[1 - cr][j];
			}
		}
		cr = 1 - cr;
	}

	cout << dp[1 - cr][w] << "\n";

}