#include <fstream>

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

int N, G;
int QMAX;

struct object {
	int weight;
	int quality;
};

object* knapsack; 

short* included; 

void solution() {
	object temp;

	temp.weight = 0;
	temp.quality = 0;

	for (int i = 0;i < N;i ++) {
		if (included[i]) {
			temp.weight += knapsack[i].weight;
			temp.quality += knapsack[i].quality;
		}
	}

	// isSol
	// if (temp.weight <= G) {

	// is Max sol ? 
	if (temp.quality > QMAX)
		QMAX = temp.quality;
	// }

}

// O(2^n)
void backtracking(int k, int GmaxSoFar) {
	if (k == N) {
		solution();
	} else {
		for (int i = 0;i < 2;i ++) {
			included[k] = i;
			GmaxSoFar += knapsack[k].weight * included[k];
			if (GmaxSoFar <= G)
				backtracking(k + 1, GmaxSoFar);
		}
	}
}

int main() {
	fin >> N >> G;

	knapsack = new object[N];
	included = new short[N];


	for (int i = 0;i < N;i ++) {
		fin >> knapsack[i].weight >> knapsack[i].quality;
	}

	
	backtracking(0, 0);

	// fout << N << ' ' << G << std :: endl;

	// for (int i = 0;i < N;i ++) {
	// 	fout << knapsack[i].weight << ' ' <<  knapsack[i].quality << std :: endl;
	// }


	fout << QMAX << std :: endl;

	return 0;
}