#include<iostream>
#include<fstream>
using namespace std;



int W[5001],K[5001],N,G,A[5001][5001];
ifstream in("rucsac.in");
ofstream out("rucsac.out");

void citire()
{
	in>>N>>G;

	for(int i=1;i<=N;i++)
	{
		in>>W[i]>>K[i];
		
	}
	
}

int R(int n,int g)
{
	for(int i=0;i<=n;i++)
		for(int w=0;w<=g;w++)
		{
			if(i==0 || w==0)
				A[i][w]=0;
			else
				if(W[i] > w)
					A[i][w]=A[i-1][w];
				else
				{
					A[i][w]=max(A[i-1][w-W[i]] + K[i] ,A[i-1][w]);
				}
		}
	 return A[n][g];
}

int main()
{
	citire();
	out<<R(N,G);
	in.close();
	out.close();
	return 0;
}