#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

using VI = vector<int>;

int n, G;
VI w, p, dp;

void read();
void solve();

int main() {
  read();
  solve();
  return 0;
}

void solve() {
  int ans = 0;

  for (int i = 1; i <= n; ++i) {
    for (int j = G - w[i]; j >= 0; --j) {
      if (dp[j + w[i]] < dp[j] + p[i]) {
        dp[j + w[i]] = dp[j] + p[i];
        ans = max(ans, dp[j + w[i]]);
      }
    }
  }

  cout << ans << '\n';
}

void read() {
  fin >> n >> G;
  w = p = dp = VI(n + 1);

  for (int i = 1; i <= n; ++i) {
    fin >> w[i] >> p[i];
  }
}