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

using namespace std;

int N,G,m[Nmax][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 = 0 ; j <= G; j++) {
			if ( j >= g[i] ) {
				m[i][j] = max(m[i-1][j],m[i-1][j-g[i]] + c[i]);
			} else {
				m[i][j] = m[i-1][j];
			}
		}
	}
}

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