#include <iostream>
#include <fstream>

const int GMAX = 1e4;

int dp[2][1 + GMAX];

inline int max(int a, int b)
{
  if (a >= b)
    return a;
  else
    return b;
}

int main() {
  std::ifstream in("rucsac.in");
  std::ofstream out("rucsac.out");
  int n, g, w, p, lin = 1;

  in >> n >> g;
  for (int i = 1; i <= n; ++i, lin = 1 - lin) {
    in >> w >> p;

    for (int j = 1; j < w; ++j)
      dp[lin][j] = dp[1 - lin][j];

    for (int j = w; j <= g; ++j)
      dp[lin][j] = max(dp[1 - lin][j], dp[1 - lin][j - w] + p);
  }

  int ans = dp[1 - lin][1];
  for (int j = 2; j <= g; ++j)
    ans = max(ans, dp[1 - lin][j]);

  out << ans;

  return 0;
}