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

#define weight first
#define cost second

const int MAXSIZE = 5000;

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

int objects,capacity;
pair<int,int> object[MAXSIZE+1];
vector<int> previous,current;

int main() {
	in >> objects >> capacity;

	for(int i=1;i<=objects;i++)
		in >> object[i].weight >> object[i].cost;

	previous.resize(capacity+1);
	current.resize(capacity+1);

	for(int i=1;i<=objects;i++) {
		for(int k=0;k<=capacity;k++) {
			current[k] = previous[k];
			if(k >= object[i].weight)
				current[k] = max(current[k],previous[k - object[i].weight] + object[i].cost);
		}
		current.swap(previous);
	}

	out << previous[capacity] << "\n";

	return (0);
}