#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX = 1e4 + 10;
const int GMAX = 5e3 + 10;

int n, G, sol;
int w[NMAX], p[NMAX];
int a[3][GMAX];

int main() 
{
	f >> n >> G;
	for(int i = 1; i <= n; i++)
		f >> w[i] >> p[i];
	int l = 0;
	for(int i = 1; i <= n; i++, l = 1 - l)
		for(int j = 0; j <= G; j++)
		{
			a[1 - l][j] = a[l][j];
			if(w[i] <= j)
				a[1 - l][j] = max(a[1 - l][j], a[l][j - w[i]] + p[i]);
		}
	g << a[l][G];
}