#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[NM][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[i][j] = max(M[i - 1][j - V[i].g]+V[i].v, M[i-1][j]);
			}
		}
	}
	fout << M[n][m];
	return 0;
}