/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int g[10001],p[10001],dp[10001][10001],n,G;
int main()
{
	fin>>n>>G;
	for(int i=1; i<=n; i++)
	{
		fin>>g[i]>>p[i];
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=G; j++)
		{

			dp[i][j] = dp[i-1][j];
			if (j >= g[i]) {
				dp[i][j] = max(dp[i][j], dp[i-1][j - g[i]] + p[i]);
			}


		}
	}
	fout<<dp[n][G];
}