#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int rucsac(const int N, const int G, const vector<int> &weight, const vector<int> &val) {
  vector<vector<int> > dp;
  for(int i = 0; i < 2; i++) {
    dp.push_back(vector<int>(G + 1));
  }

  for(int i = 1; i <= N; i++) {
    int curr = i % 2;
    int prev = (i+1)%2;
    for(int w = 1; w <= G; w++) {
      int new_w = 0;
      if(w >= weight[i - 1]) {
        new_w = val[i-1] + dp[prev][w - weight[i-1]];
      }
      dp[curr][w] = max(new_w, dp[prev][w]);
    }
  }
  return dp[N % 2][G];
}

int main() {
  ifstream in("rucsac.in");
  ofstream out("rucsac.out");
  int N, G, w, v;
  vector<int> weight, val;
  in >> N >> G;
  
  for(int i = 0; i < N; i++) {
    in >> w >> v;
    weight.push_back(w);
    val.push_back(v);
  }

  out << rucsac(N, G, weight, val);

  return 0;
}