#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX = 10010;
const int GMAX = 5010;

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

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