#include <iostream>
#include <fstream>
#include <cstring>

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;

  in >> n >> g;

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

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

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

    memcpy(dp[0], dp[1], sizeof(dp[0]));
  }

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

  out << ans;

  return 0;
}