qwedf

//完全背包II
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 10;
int w[N], v[N];
long long f[2][100010];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j >= w[i]) f[i % 2][j] = max(f[(i - 1) % 2][j], v[i] + f[i % 2][j - w[i]]);
			else f[i % 2][j] = f[(i - 1) % 2][j];
		}
	}
	cout << f[n%2][m];
	return 0;
}