#include<iostream>
#include<fstream>

using namespace std;

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

int W[5010], P[5010], D[2][10010];

inline int mx(int a, int b)
{
	if(a > b)
		return a;
	return b;
}

int main()
{
	int N, G, i, j, k = 0;
	
	in >> N >> G;
	
	for(i = 1; i <= N; ++i)
		in >> W[i] >> P[i];
	
	for(i = 1; i <= N; ++i, k ^= 1)
		for(j = 0; j <= G; ++j){
			D[k ^ 1][j] = D[k][j];
			
			if(W[i] <= j)
				D[k ^ 1][j] = mx(D[k ^ 1][j], D[k][ j - W[i] ] + P[i]);
		}
		
	out << D[k][G];
	
	return 0;
}