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

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

int N, G, Pmax;
int W[5010], P[5010];
int D[2][10010];

int main()
{


	
	fin >> N >> G;
	for (int i = 1; i <= N; ++i)
		fin >>W[i]>>P[i];

	
	int l = 0;
	for (int i = 1; i <= N; ++i, l = 1 - l)
		for (int cw = 0; cw <= G; ++cw)
		{
			
			D[1 - l][cw] = D[l][cw];

			
			if (W[i] <= cw)
				D[1 - l][cw] = max(D[1 - l][cw], D[l][cw - W[i]] + P[i]);
		}


	Pmax = D[l][G];

	
	fout << Pmax;

	return 0;
}