#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAXN 5010
#define MAXG 10100

int d[2][MAXG], n, g;
vector<pair<int, int> > obj;

int main()
{
	fstream fin("rucsac.in", ios::in);
	fstream fout("rucsac.out", ios::out);

	fin >> n >> g;
	obj.resize(n);
	
	for (int i = 0; i < n; ++i) {
		fin >> obj[i].first >> obj[i].second;
	}
		
	for (int i = 0; i < n; ++i) {
		for (int w = 0; w <= g; ++w) {
			d[1][w] = d[0][w];

			if (w >= obj[i].first) {
				d[1][w] = max(d[1][w], d[0][w - obj[i].first] + obj[i].second);
			}
		}
		
		memcpy (d[0], d[1], MAXG * sizeof(int));
	}
	
	fout << d[0][g] << endl;
	
	fin.close();
	fout.close();	
	return 0;
}