#define MAX_N 1000
#define MAX_G 5000

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

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

int n, gMax, G[MAX_N + 1], V[MAX_N + 1], PD[MAX_N + 1][MAX_G + 1];

int main()
{
	fin >> n >> gMax;
	for (int i = 1; i <= n; ++i)
	{
		fin >> G[i] >> V[i];
	}
	
	for (int i = 1; i <= n; ++i)
	{
		for (int g = 0; g <= gMax; ++g)
		{
			if ((g + G[i]) <= gMax)
			{
				PD[i][g + G[i]] = max(max(PD[i][g + G[i]], PD[i - 1][g] + V[i]), PD[i - 1][g + G[i]]);
			}
			else
			{
				PD[i][g] = max(PD[i][g], PD[i - 1][g]);
			}
		}
	}
	
	fout << PD[n][gMax];
	
	fin.close();
	fout.close();
	return 0;
}