#include <iostream>
#include <fstream>
#define NMAX 5005
#define GMAX 10005
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int opt[2][GMAX];

int main () 
{
	int n, v;
	fin >> n >> v;
	for (int i = 0; i <= 1; ++i) {
		for (int j = 1; j <= v; ++j) {
			opt[i][j] = -1;
		}
	}
	int maxn = 0;
	int x, y;
	for (int i = 1; i < n; ++i) {
		fin >> x >> y;
		for (int j = 1; j < x; ++j) {
			opt[i%2][j] = max(opt[i%2][j],opt[(i-1)%2][j]);
		}
		for (int j = x; j <= v; ++j) {
			if (opt[(i-1)%2][j-x] != -1) {
				opt[i%2][j] = opt[(i-1)%2][j-x] + y;
			}
			opt[i%2][j] = max(opt[i%2][j],opt[(i-1)%2][j]);
		}
	}
	fin >> x >> y;
	for (int j = 1; j < x; ++j) {
		opt[n%2][j] = max(opt[n%2][j],opt[(n-1)%2][j]);
	}
	for (int j = x; j <= v; ++j) {
		if (opt[(n-1)%2][j-x] != -1) {
			opt[n%2][j] = opt[(n-1)%2][j-x] + y;
		}
		opt[n%2][j] = max(opt[n%2][j],opt[(n-1)%2][j]);
		if (opt[n%2][j] > maxn) {
			maxn = opt[n%2][j];
		}
	}
	fout << maxn;
	/*for (int i = 0; i <= 1; ++i) {
		for (int j = 1; j <= v; ++j) {
			cout << opt[i][j] << " ";
		}
		cout << endl;
	} */
	
	return 0;
}