#include <fstream>

using namespace std;

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

int n, g, w, c;
int dp[2][10005];

int main()	{
  fin >> n >> g;
  for (int i = 1; i <= n; ++i)	{
		fin >> w >> c;
		for (int j = w; j <= g; ++j)	{
			dp[i & 1][j] = max(dp[1 - i & 1][j], dp[1 - i & 1][j - w] + c);
		}
  }
  fout << dp[n & 1][g];
  return 0;
}