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

int dp(int, int, vector<int>cx);
int n, w;
int* ws2;
int* vs2;
int* d;
int main() {
  cin >> n >> w;
  ws2 = new int[n];
  vs2 = new int[n];
  d = new int[w+1];
  for (int i = 0; i < n; i++) {
    cin >> ws2[i] >> vs2[i];
  }
  for (int i = 0; i < w+1; i++) {
    d[i] = -1;
  }
  vector<int> vis;
  for (int i = 0; i < n; i++) {
    vis.push_back(0);
  }
  int ans = dp(n, w, vis);
  cout << ans << endl;

}

int dp(int layer, int curw, vector<int> vis) {
  int& ans = d[curw];
  if (ans >= 0) { return ans; }
  if (layer < 0) { return 0;}
  ans = 0;
  for (int i = 0; i < n; i++) {
    if (curw - ws2[i] >= 0 && vis[i] == 0) {
      vis[i] = 1;
      ans = max(dp(layer-1, curw, vis), dp(layer-1, curw - ws2[i], vis) + vs2[i]);
    }
  }
  return ans;
}
  