#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,greutati[5001],profit[5001],i,j,l,D[2][10001];


int main()
{
	fin >> n >> g ;
	for (i=1;i<=n;i++)
	{
		fin >> greutati[i] >> profit[i];
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=g;j++)
		{
			if (j-greutati[i]>=0)D[i%2][j]=max(D[(i-1)%2][j],D[(i-1)%2][j-greutati[i]]+profit[i]);
			else D[i%2][j]=D[(i-1)%2][j];
		}
	}
	fout << D[n%2][g] << "\n";
	return 0;
}