#include <fstream>
#include <vector>

using namespace std;

#define N 5000

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

struct state
{
	int w;
	int p;
};

vector<state> interclasare(vector<state> S, vector<state> T, int M)
{
	vector<state> Sn;
	Sn.push_back(S[0]);

	int j = 1;
	int k = 0;
	int lp = 0;

	while (j < S.size() && k < T.size())
	{
		if (S[j].w < T[k].w)
		{
			if (S[j].p > lp && S[j].w <= M)
			{
				Sn.push_back(S[j]);
				lp = S[j].p;
			}
			j++;
		}
		else if (T[k].w < S[j].w)
		{
			if (T[k].p > lp && T[k].w <= M)
			{
				Sn.push_back(T[k]);
				lp = T[k].p;
			}
			k++;
		}
		else
		{
			if (T[k].p > lp && T[k].p > S[j].p && T[k].w <= M)
			{
				Sn.push_back(T[k]);
				lp = T[k].p;
			}
			else if (S[j].p > lp && S[j].p > T[k].p && S[j].w <= M)
			{
				Sn.push_back(S[j]);
				lp = S[j].p;
			}
			j++;
			k++;
		}
	}
	while (j < S.size())
	{
		if (S[j].p > lp && S[j].w <= M)
		{
			Sn.push_back(S[j]);
			lp = S[j].p;
		}
		j++;
	}
	while (k < T.size())
	{
		if (T[k].p > lp && T[k].w <= M)
		{
			Sn.push_back(T[k]);
			lp = T[k].p;
		}
		k++;
	}

	return Sn;
}

void rucsac(int M, const int n, int* p, int* w)
{
	vector<state> s;
	state temp = { 0, 0 };
	s.push_back(temp);
	vector<state> t;
	temp.w = w[0]; temp.p = p[0];
	t.push_back(temp);


	for (int i = 1; i <= n; ++i)
	{
		s = interclasare(s, t, M);

		for (int j = 0; j < s.size(); ++j)
		{
			temp.w = s[j].w + w[i];
			temp.p = s[j].p + p[i];
			if (j < t.size())
				t[j] = temp;
			else
				t.push_back(temp);
		}
	}

	int yj = s[s.size() - 1].p;
	g << yj;

}

int main(void)
{
	int p[N];
	int w[N];

	int M;
	int n;

	f >> n >> M;
	for (int i = 0; i < n; ++i)
		f >> w[i] >> p[i];

	rucsac(M, n, p, w);

	return 0;
}