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



int W[5001],K[5001],N,G,A[2][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)
{
	int k=0,nr=0;
	while(nr<=n)
	{
	  k=1-k;
		for(int w=0;w<=g;w++)
		{
				if(W[nr] > w)
					A[k][w]=A[1-k][w];
				else
				{
					A[k][w]=max(A[1-k][w-W[nr]] + K[nr] ,A[1-k][w]);
				}
		}
		nr++;
	}
	 return A[k][g];
}

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