#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<unordered_set>
#include<set>
#include<math.h>
using namespace std;
int n, G, mat[5010][3],dp[3][10010],i,linie,j;
int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	f >> n>> G;
	for (i = 1; i <= n; i++)
	{
		f >> mat[i][1] >> mat[i][2];
	}
	linie = 1;
	for (i = 1; i <= n; i++)
	{
		for (j = 0; j <= G; j++)
		{
			if (linie == 2)
			{
				dp[linie - 1][j] = dp[linie][j];
				if (mat[i][1] <= j)
					dp[linie - 1][j] = max(dp[linie - 1][j], dp[linie][j - mat[i][1]] + mat[i][2]);
			}
			else
			{
				dp[linie + 1][j] = dp[linie][j];
				if (mat[i][1] <= j)
					dp[linie + 1][j] = max(dp[linie + 1][j], dp[linie][j - mat[i][1]] + mat[i][2]);
			}
		}
		if (linie == 2)
			linie = 1;
		else
			linie = 2;
	}
	g << dp[linie][G];
	return 0;
}