#include<iostream>
#include<map>
using namespace std;
#define int long long
int n, wmax;
int v[5000], w[5000];

map<pair<int, int>, int> mm;
int fun(int i, int wsum){
  if(i==n) return 0;
  pair<int, int> k={i, wsum};
  if(mm.count(k)) return mm[k];
  int ret=fun(i+1, wsum);
  if(wsum+w[i]<=wmax) ret=max(ret, fun(i+1, wsum+w[i])+v[i]);
  return mm[k]=ret;
}

signed main(){

  cin>> n>> wmax;
  for(int i=0; i<n; i++) cin>> v[i]>> w[i];

  cout<< fun(0, 0)<< endl;

  return 0;
}