#include<iostream>
#include<fstream>

using namespace std;

short rezolvare(short *, short *, short, short);

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

	if (&f == NULL || &g == NULL)
	{
		cout << "Eroare deschidere fisiere \n";
		exit(1);
	}

	short n, wt_max;

	f >> n >> wt_max;

	short *wt, *val;
	wt = new short[n];
	val = new short[n];

	for (short i = 0; i < n; i++)
		f >> wt[i] >> val[i];

	g << rezolvare(wt, val, n, wt_max);

	delete[] wt;
	delete[] val;

	f.close();
	g.close();

	return 0;
}

short max(short a, short b)
{
	return (a > b) ? a : b;
}

short rezolvare(short *wt, short *val, short n, short wt_max)
{
	short **a;

	a = new short*[n];

	for (short i = 0; i < n; i++)
		a[i] = new short[wt_max + 1], a[i][0] = 0;

	for (short i = 0; i < n; i++)
	for (short j = 0; j < wt_max + 1; j++)
	{
		if (j < wt[i])
		{
			if (i == 0)
				a[i][j] = 0;
			else
				a[i][j] = a[i - 1][j];
		}
		else if (i == 0)
			a[i][j] = val[i];
		else
			a[i][j] = max(a[i - 1][j], val[i] + a[i - 1][j - wt[i]]);
	}

	short answer = 0;
	for (short j = 0; j < wt_max + 1;j++)
	if (a[n - 1][j]>answer)
		answer = a[n - 1][j];

	for (short i = 0; i < n; i++)
		delete[] a[i];

	delete[] a;
	
	return answer;

}