#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in"); ofstream fout ("rucsac.out");
int W[5001], P[5001], Optim[10001], n, G;

int main()
{
	fin >> n >> G;
	for (int i = 1; i <= n; i++)
		fin >> W[i] >> P[i];
	Optim[0] = 0;
	int sol = 0;
	for (int i = 1; i <= n; i++)
		for (int j  = G - W[i]; j >= 0; --j)
		{
			if (Optim[j + W[i]] < Optim[j] + P[i])
			{
				Optim[j + W[i]] = Optim[j] + P[i];
				if (Optim[j + W[i]] > sol) sol = Optim[j + W[i]];
			}
		}
	fout << sol;
	return 0;
}