#include<fstream>
#include<iostream>
using namespace std;
int n,g,w[5010],p[5010],a[5010][10010];

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	in>>n>>g;
	for(int i=1;i<=n;i++)
	{
		in>>w[i]>>p[i];
	}
	in.close();
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=g;j++)
		{
			a[i][j]=a[i-1][j];
			if(j>=w[i])
			{
				a[i][j]=max(a[i-1][j], a[i-1][j-w[i]]+p[i]);
			}
		}
	}
	
	out<<a[n][g];
	return 0;
}