#include <iostream>
#include <iomanip>
#include <fstream>

//#define DEBUG true

#define NRO 5005
#define GRMAX 10005
using namespace std;

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

int w[NRO],p[NRO],G, n, a[GRMAX], b[GRMAX];

int main(){
	fin >> n >> G;
	for(int i=1;i<= n;i++)
		fin >> w[i] >> p[i];
	int * cp = a, * cc = b;
	for(int j=0;j<=G;j++)
		cp[j] = 0; // cu zero obiecte castigul este zero, indiferent de greutatea j
	for(int i=1;i<=n;i++)
	{
		cc[0] = 0; // cu greaute zero castigul este zero, indiferent de numarul de obiecte
		for(int j=1;j<=G;j++)
		{
			cc[j] = cp[j]; // nu punem obiectul i in rucsac
			if(w[i]<=j) // obiectul i incape in rucsac
				if(cc[j] < cp[j-w[i]] + p[i])
					cc[j] = cp[j-w[i]] + p[i];
		}
		int * aux = cc;
		cc = cp;
		cp = aux;
	}
	fout <<cp[G];
	

return 0;
}