#include <fstream>
using namespace std;
int w[10001], p[10001], v[10001];
int main()
{
	int n, g, i, j, s = 0;
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	cin >> n >> g;
	for (i = 1; i <= n; i++)
		cin >> w[i] >> p[i];
	for (i = 1; i <= n;i++)
	for (j = g - w[i]; j >= 0; j--)
	{
		if (v[j + w[i]]<v[j] + p[i])
			v[j + w[i]] = v[j] + p[i];
		if (v[j + w[i]]>s)s = v[j + w[i]];
	}
	cout << s;


	return 0;
}