#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
// ??\???????????????
const int MAX_N = 100;		// ????????°?????????
const int MAX_W = 10000;	// ????????????????????????
 
// ??\??????
int N; // ???????????°
int W; // ????????????????????¶?´??????¶???
int Weight[MAX_N];	// ??????n?????????
int Value[MAX_N];	// ??????n?????????
 
 
//---------- ???????????¢?´¢ ----------
int MaxValueEdakari;	// ??????????????§
void dfsEdakari(int n, int totalWeight, int totalValue)
{
	// ???????????????????????????????????§????¶?????????¨??????????????????
	if(totalWeight>W)
	{
		return;
	}
 
	// ????????????????????¨??¨??????????????¨??£?????¨??????????????????????????§?????´??°??§???????????¨??????????????§??????????????§?????????
 
	if(n==N)
	{
		// ??¨??¨???????????????????????§????????§???????????´??°
		MaxValueEdakari = max(MaxValueEdakari,totalValue);
		return;
	}
 
	dfsEdakari(n+1, totalWeight+Weight[n], totalValue+Value[n]); // ??????n?????????
	dfsEdakari(n+1, totalWeight, totalValue); // ??????n???????????????
}
 
//---------- ?????¢????????° ----------
int dp[MAX_N][MAX_W]; // dp[n][totalWeight=??????n???N-1?????????????¨??????????]=??????n???N-1???????????????????¨?????????§???
int dfsMemo(int n, int totalWeight)
{
	if(n==N)
	{
		// ?????????1??????????????§???????????§????????????0
		return 0;
	}
 
	int& memo = dp[n][totalWeight]; // ??¢??°?????\??????n,totalWeight???????????????????????????index???????????????????????????
 
	if(memo>=0)
	{
		// ?????§?????¢??°???????????????????¨???????????????¢????????????????????§??????return;
		return memo;
	}
 
	// ?????¢?????????
	memo=0;
 
	// ??????
	if(totalWeight+Weight[n]<=W) // ?????????????????§??????
	{
		memo = max(memo,dfsMemo(n+1, totalWeight+Weight[n])+Value[n]);
	}
 
	// ????????????
	memo = max(memo,dfsMemo(n+1, totalWeight));
 
	return memo;
}
 
 
int main()
{
	// ??\???
	cin >> N >> W;
	for (int n = 0; n < N; n++)
	{
		cin >> Weight[n] >> Value[n];
	}
 
	//---------- ???????????¢?´¢ ----------
	MaxValueEdakari = -1;
	dfsEdakari(0,0,0);
 
	//---------- ?????¢????????° ----------
	for (int n = 0; n < MAX_N; n++)
	{
		for (int w = 0; w < MAX_W; w++)
		{
			dp[n][w]=-1;
		}
	}
	const int MaxValueMemo = dfsMemo(0,0);
 
	// ??????
	cout << " MaxValueEdakari=" << MaxValueEdakari << " MaxValueMemo=" << MaxValueMemo << endl;
 
	return 0;
}