#include <iostream>
#include <fstream>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#endif

#define endl '\n'

const int NMAX = 5005;
const int GMAX = 10005;

int n, g;
int w[NMAX], p[NMAX];
int dp[2][GMAX];

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

void solve() {
  for (int i = 1; i <= n; i++) {
    bool row = i % 2;
    for (int j = 1; j <= g; j++) {
      if (j - w[i] >= 0)
        dp[row][j] = max(dp[!row][j], dp[!row][j - w[i]] + p[i]);
      else
        dp[row][j] = dp[row][j];
    }
  }
  fout << dp[n % 2][g];
}

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