#include <fstream>
using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n, m, g[5000 + 10], v[5000 + 10], matrice[2+10][10000 + 10];

void citire()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> g[i] >> v[i];
}

void rezolvare()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			matrice[2][j] = matrice[2 - 1][j];	//Se considera cazul in care solutia optima se obtine neadaugand obiectul i
			if (g[i] <= j)	//Se considera cazul in care solutia optima se obtie adaugand obiectul i
				matrice[2][j] = max(matrice[2][j], matrice[2 - 1][j - g[i]] + v[i]);
		}
		for (int j = 0; j <= m; j++)
			matrice[1][j] = matrice[2][j];
	}
	cout << matrice[2][m];
}


int main()
{
	citire();
	rezolvare();
	return 0;
}