#include<iostream>
#include<fstream>

using namespace std;

int rezolvare(int *, int *, int, int);

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

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

	int n, wt_max;

	f >> n >> wt_max;

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

	for (int 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;
}

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

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

	a = new int*[n];

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

	for (int i = 0; i < n; i++)
	for (int 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]]);
	}

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

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

	delete[] a;
	
	return answer;

}