#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define INF		(0x3f3f3f3f)

int main ()
{
	/* code */
	std::ifstream in("rucsac.in");
	
	int N, G;
	in >> N >> G;
	
	std::vector<int> w(N+1);
	std::vector<int> p(N+1);
	
	for (int i = 1; i <= N; ++ i) {
		in >> w[i] >> p[i];
	}
	
	in.close();
	
	std::vector<std::vector<int> >d(2, std::vector<int>(G+1, -INF));
	d[0][0] = 0;
	int cur = 1, lst = 0;
	for (int i = 1; i <= N; ++ i, cur ^= 1, lst ^= 1) {
		for (int j = 0; j <= G; ++ j) {
			d[cur][j] = d[lst][j];
			if (j - w[i] >= 0) {
				d[cur][j] = std::max(d[cur][j], d[lst][j-w[i]] + p[i]);
			}
		}
	}
	
	int res = 0;
	for (int i = 0; i <= G; ++ i) {
		res = std::max(res, d[lst][i]);
	}
	
	std::ofstream out("rucsac.out");
	
	out << res << "\n";
	
	out.close();
	
	return 0;
}