#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 5e3 + 5;
const int MAX_G = 1e4 + 5;

int n, g;

int dp[2][MAX_G];

int w[MAX_N], p[MAX_N];

int main() {
  int ans, t;
  fin >> n >> g;
  for (int i = 1; i <= n; ++i) {
    fin >> w[i] >> p[i];
  }
  t = 1;
  for (int i = 1; i <= n; ++i, t = 1 - t) {
    for (int j = 1; j <= g; ++j) {
      dp[t][j] = dp[1 - t][j];
      if (j - w[i] >= 0) {
        dp[t][j] = max(dp[t][j], dp[1 - t][j - w[i]] + p[i]);
      }
    }
  }
  fout << dp[1 - t][g] << "\n";
  return 0;
}