#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main() {

	ifstream fin("rucsac.in");
	int N, G;
	fin >> N >> G;
	int g[10000], p[10000];
	for (int i = 1; i <= N; i++)
		fin >> g[i] >> p[i];
	fin.close();

	int d[10000][10000];//d[ob][greutate]
	d[0][0] = 0;
	for (int i = 0; i <= G; i++)
        d[0][i] = -99999;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= G; j++) {
			if (j - g[i-1] >= 0) d[i][j] = max(d[i - 1][j], d[i - 1][j - g[i-1]] + p[i-1]);
                else d[i][j] = d[i - 1][j];
		}
	}

	ofstream fout("rucsac.out");
	//fout << d[N-1][G];
	int maxim = 0;
	for (int i = 0; i <= G; i++) {
		if (d[N][i] > maxim)
            maxim = d[N][i];
	}
	fout << maxim;
	fout.close();

	//system("PAUSE");
	return 0;
}