#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 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)
				M[1][j] = M[1][j] > M[1][j - 1] ? M[1][j] : M[1][j - 1];
			M[1][j] = M[1][j] > M[0][j] ? M[1][j] : M[0][j];
		}
		for (j = 0; j <= m; j++)
		{
			M[0][j] = M[1][j];
		}
	}
	fout << M[0][m];
	return 0;
}