#include<fstream>
#include<iostream>

using namespace std;

long maxi(long x,long y)
{
	if(x>=y)
		return x;
	return y;
}

int main()
{
	int n,g,i,j,x,y;
	ifstream f("rucsac.in");
	ofstream h("rucsac.out");
	f>>n>>g;
	long d[2][g+1];
	for(i=0;i<=1;i++)
		for(j=0;j<=g;j++)
			d[i][j]=0;
	for(i=0;i<=n-1;i++)
	{
		f>>x>>y;
		if(i%2==0)
		{
			for(j=1;j<=g;j++)
			{
				if(j<x)
					d[1][j]=d[0][j];
				else
					d[1][j]=maxi(d[0][j],d[0][j-x]+y);
			}
		}
		else
		{
			for(j=1;j<=g;j++)
			{
				if(j<x)
					d[0][j]=d[1][j];
				else
					d[0][j]=maxi(d[1][j],d[1][j-x]+y);
			}
		}
	}
	h<<maxi(d[0][g],d[1][g]);
	h.close();
	return 0;
}