#include<fstream>
using namespace std;

int v[10],N,G,W[5001],P[5001];
int d[5001][10001];

ifstream fin("permutari.in");
ofstream fout("permutari.out");


int main()
{
fin>>N>>G;
for(int i=1;i<=N;i++)
	fin>>W[i]>>P[i];

for(int i=1;i<=N;i++)
	for(int j=0;j<=G;j++)
	{
		d[i][j]=d[i-1][j];
		if(W[i]<=j && d[i][j]<(d[i-1][j - W[i]] + P[i]))
			d[i][j]=d[i-1][j-W[i]]+P[i];
	}
	
fout<<d[N][G];
}