#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;

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

int N, G;

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

// result
int result;

void read() {

	fin >> N >> G;

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

int set_dp(int max_weight, int item) {

	if (max_weight * item == 0)
		return 0;
	
	if (weight[item] > max_weight)
		return set_dp(max_weight, item - 1);
	else
		return max(price[item] + set_dp(max_weight - weight[item], item - 1), set_dp(max_weight, item - 1));
}

void solve() {

	result = set_dp(G, N);
}

void display() {
	
	fout << result;
}

int main() {

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

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

	return 0;
}