using namespace std;
#include<iostream>
#include<fstream>

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

int ga,n;
int wg[5001],pg[5001];
int dp[10000];

int main()
{
	f>>n;
	f>>ga;
	int i;
	for(i=1; i<=n; i++)
	{
		f>>wg[i]>>pg[i];
	}
	int s=0;

	    for(i = 1; i <= n; ++i)
			for( int j=ga-wg[i]; j >= 0; --j)
			{
				if( dp[j+wg[i]]<dp[j]+pg[i] )
				{
					dp[j+wg[i]] = dp[j] + pg[i];
					if( dp[j+wg[i]] > s)
						s=dp[j+wg[i]];
				}
			}

	g<<s;
}