#include<iostream>
#include<fstream>
#define Nmax 5001
#define Gmax 10001

using namespace std;

int N,G,m[Gmax],g[Nmax],c[Nmax];

void citire() {
	ifstream f("rucsac.in");
	f >> N;
	f >> G;
	for(int i = 1; i <= N; i++) {
		f >> g[i];
		f >> c[i];
	}
	f.close();
}

void creareMatrice() {
	for(int i = 1; i <= N; i++) {
		for(int j = G ; j >= g[i]; j--) {
			if ( j >= g[i] ) {
				m[j] = max(m[j],m[j-g[i]] + c[i]);
			}
		}
	}
}

int main()
{
	citire();
	creareMatrice();
	ofstream g("rucsac.out");
	g << m[G];
	g.close();
	return 0;
}