#include <fstream>
#define NM 5005

using namespace std;

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

struct obiect { int v, g; };

obiect V[NM];

int n, m, M[2][10000];

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int i, j;
	fin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		fin >> V[i].g >> V[i].v;
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 0; j <= m; j++)
		{
			if (j - V[i].g >= 0)
			{
				M[1][j] = M[0][j - V[i].g]+V[i].v;
			}
			if (j-1 >= 0)
				M[1][j] = max(M[1][j], M[1][j - 1]);
			M[1][j] = max(M[1][j], M[0][j]);
		}
		for (j = 0; j <= m; j++)
		{
			M[0][j] = M[1][j];
		}
	}
	fout << M[0][m];
	return 0;
}