#include<fstream>

using namespace std;

int dp[2][10001];
ifstream in("rucsac.in");
ofstream out("rucsac.out");

int main(){

	int n,g;
	in>>n>>g;
	int greutate[n+1],profit[n+1];
	greutate[0]=0;
	profit[0]=0;
	for(int i=1;i<=n;i++)
	{
		in>> greutate[i] >> profit[i];
	}
	for(int i=0;i<=n;i++)
	{
		if(i%2!=0)
		{
			for(int j=0;j<=g;j++)
			{
				if(greutate[i]<=j)
				{
					dp[1][j]=max(dp[0][j], dp[0][j-greutate[i]]+profit[i]);
				}
				else
				{
					dp[1][j]=dp[0][j];
				}
			}
		}
		else
		{
			for(int j=0;j<=g;j++)
			{
				if(greutate[i]<=j)
				{
					dp[0][j]=max(dp[1][j], dp[1][j-greutate[i]]+profit[i]);
				}
				else
				{
					dp[0][j]=dp[1][j];
				}
			}
		}
	}
	if(n%2==0)
	{
		out<<dp[0][g];
	}
	else
	{
		out<<dp[1][g];
	}

	return 0;
}