#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>

#define INF 0x3F3F3F3F

using namespace std;

const string FILE_NAME = "rucsac";
const int N_MAX = 5e3 + 1;
const int G_MAX = 1e4 + 1;

ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");

int N, G;

int weight[N_MAX];
int price[N_MAX];

// dynamic programming
int DP[G_MAX];
bool visited_w[G_MAX];

// result
int result;

void read() {

	fin >> N >> G;

	for (int i = 1; i <= N; i++)
		fin >> weight[i] >> price[i];
}

void solve() {

	visited_w[0] = true;

	for (int i = 1; i <= N; i++)
		for (int j = G - weight[i]; j >= 0; j--)
			if (visited_w[j] == true) {
			
				if (visited_w[j + weight[i]] == false)
					visited_w[j + weight[i]] = true,
					DP[j + weight[i]] = DP[j] + price[i];
				else
					DP[j + weight[i]] = max(DP[j + weight[i]], DP[j] + price[i]);

				result = max(result, DP[j + weight[i]]);
			}
}

void display() {
	
	fout << result;
}

int main() {

	read();
	solve();
	display();

	fin.close();
	fout.close();

	return 0;
}