#include<fstream>
#include<algorithm>
using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int D[2][10010],N,G;
int W[5010], P[5010];
int main()
{
	in >> N >> G;

	for (int i = 1;i <= N;++i)
		in >> W[i] >> P[i];
	for (int i = 1;i <= N;++i)
		for (int j = 1;j <= G;++j)
			if (W[i] > j)
				D[i%2][j] = D[(i+1)%2][j];
			else
				D[i%2][j] = max(D[(i+1)%2][j], D[(i+1)%2][j - W[i]] + P[i]);

	out << D[N%2][G];

	return 0;
}