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

struct obiect{
	int w, val;
};

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

signed main() {
	freopen("rucsac.in", "r", stdin);
	freopen("rucscac.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;
	}

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

	cout << dp[n][w] << "\n";

}