#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;
  fin >> n >> g;
  for (int i = 1; i <= n; ++i) {
    fin >> w[i] >> p[i];
  }
  dp[0][0] = 0;
  ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = w[i]; j <= g; ++j) {
      dp[i % 2][j] = dp[1 - i % 2][j];
      dp[i % 2][j] = max(dp[i % 2][j], dp[1 - i % 2][j - w[i]] + p[i]);
      if (i == n) {
        ans = max(ans, dp[i % 2][j]);
      }
    }
  }
  fout << ans << "\n";
  return 0;
}