#include <fstream>

using namespace std;

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

const int MAXN = 5e3;
const int MAXG = 5e4;

long long int dp[MAXG + 1];
int n, g, w, p;

int main() {
  in >> n >> g;

  while (n --) {
    in >> w >> p;
    for (int i = g; i >= w; -- i) {
      dp[i] = max(dp[i], dp[i - w] + p);
    }
  }
  out << dp[g];

  return 0;
}