#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#include <memory>
#include <limits>
#include <fstream>

#include <vector>
#include <unordered_map>
#include <memory>
#include <array>
#include <stack>

template<class PROBLEM, class STATE>
class BBZDD {
public:
	struct Node {
		STATE state;
		STATE value;
		int level;
		std::vector<std::weak_ptr<Node>> par;
		std::array<std::shared_ptr<Node>, 2> ch;
	};
private:
	std::vector<std::unordered_map<STATE, std::shared_ptr<Node>>> hashTable;
	std::stack<std::shared_ptr<Node>> unsearchedNodes;
	std::shared_ptr<Node> rootNode;
	std::shared_ptr<Node> zeroNode, oneNode;
	int cntNode;
	int visitedNode;
	STATE lowerBound;
public:
	virtual int getRoot(STATE& state) const = 0;
	virtual int getChild(STATE& state, STATE& V, int level, int value) const = 0;
	std::shared_ptr<Node> getRootNode() const { return rootNode; }
	std::shared_ptr<Node> getZeroNode() const { return zeroNode; }
	std::shared_ptr<Node> getOneNode() const { return oneNode; }
	STATE getLowerBound() const { return lowerBound; }
	void setLowerBound(STATE value) { lowerBound = value; }
	void updateLowerBound(STATE value) {
		if (lowerBound < value) {
			lowerBound = value;
			//std::cout << "update : " << lowerBound << std::endl;
		}
	}
	int getCntNode() const { return cntNode; }
	int getVisitedNode() const { return visitedNode; }

	void clear() {
		rootNode.reset();
		zeroNode.reset();
		oneNode.reset();
		while (!unsearchedNodes.empty()) unsearchedNodes.pop();
		hashTable.clear();
	}

	void construct() {
		clear();

		{ // initialize nodes
			rootNode = std::make_shared<Node>();
			zeroNode = std::make_shared<Node>();
			oneNode = std::make_shared<Node>();

			cntNode = 1;
			visitedNode = 1;
			lowerBound = 0;
		}

		int n;
		{ // initialize hashTable
			n = this->getRoot(rootNode->state);
			rootNode->value = 0;
			rootNode->level = n;
			zeroNode->value = std::numeric_limits<STATE>::lowest();
			oneNode->value = 0;
			lowerBound = std::numeric_limits<STATE>::lowest();

			hashTable.resize(n + 1);
			hashTable[n][rootNode->state] = rootNode;
			unsearchedNodes.push(rootNode);
		}

		{ // search
			while (!unsearchedNodes.empty()) {
				auto nowNode = unsearchedNodes.top(); unsearchedNodes.pop();
				++visitedNode;

				for (int value = 0; value < 2; ++value) {
					STATE chState = nowNode->state;
					STATE chValue = nowNode->value;
					int level = getChild(chState, chValue, nowNode->level, value);
					if (level == 0) {
						nowNode->ch[value] = zeroNode;
					}
					else if (level == -1) {
						nowNode->ch[value] = oneNode;
						updateLowerBound(chValue);
					}
					else {
						auto it = hashTable[level].find(chState);
						if (it == hashTable[level].end()) { // haven't exist yet
							auto newNode = std::make_shared<Node>();
							newNode->state = chState;
							newNode->value = chValue;
							newNode->level = level;

							nowNode->ch[value] = newNode;
							hashTable[level][chState] = newNode;
							unsearchedNodes.push(newNode);
							++cntNode;
							newNode->par.emplace_back(nowNode);
						}
						else { // already existed
							auto&& foundNode = it->second;
							nowNode->ch[value] = foundNode;
							foundNode->par.emplace_back(nowNode);
							if (foundNode->value < chValue) {
								foundNode->value = chValue;
								unsearchedNodes.push(foundNode);
							}
						}
					}
				}
			}
		}
	}
};



double magic = 1;

template<class TYPE>
class KnapsackProblem : public BBZDD<KnapsackProblem<TYPE>, TYPE> {
private:
	using Node = typename BBZDD<KnapsackProblem<TYPE>, TYPE>::Node;
	const int n;
	const TYPE W;
	const std::vector<TYPE> w;
	const std::vector<TYPE> v;
	std::vector<TYPE> orderedW;
	std::vector<TYPE> orderedV;
public:
	KnapsackProblem(int n, TYPE W, std::vector<TYPE> w, std::vector<TYPE> v) : n(n), W(W), w(w), v(v), orderedW(w), orderedV(v) {
		using P = std::pair<TYPE, TYPE>;
		std::vector<P> item(n);
		for (int idx = 0; idx < n; ++idx) item[idx] = std::make_pair(w[idx], v[idx]);
		std::sort(std::begin(item), std::end(item), [&](const P& lhs, const P& rhs) {
			return lhs.second * rhs.first > rhs.second * lhs.first;
		});
		for (int idx = 0; idx < n; ++idx) std::tie(orderedW[idx], orderedV[idx]) = item[idx];
	}

	int getRoot(TYPE& state) const override {
		state = 0;
		return n;
	}

	double getUpperBound(TYPE state, TYPE V, int level) const {
		for (int idx = level; idx > 0; --idx) {
			if (state + orderedW[n - idx] <= W) {
				state += orderedW[n - idx];
				V += orderedV[n - idx];
			}
			else {
				return V + (double)orderedV[n - idx] * (W - state) / orderedW[n - idx];
			}
		}
		return (double)V;
	}

	int getChild(TYPE& state, TYPE& V, int level, int value) const override {
		if (value) state += orderedW[n - level], V += orderedV[n - level];
		if (state > W) return 0;
		--level;
		double upperBound = getUpperBound(state, V, level);
		if (upperBound < this->getLowerBound()) return 0;
		if (level == 0) return -1;
		return level;
	}

	TYPE getValue() const {
		return this->getLowerBound();
	}
};
#include <random>
int main() {

	/*int n = 5, W = 10;
	std::vector<int> w({ 4, 4, 9, 5, 3 });
	std::vector<int> v({ 3, 4, 7, 3, 2 });*/

	using ll = long long;
	using TYPE = ll;
	int n;
	TYPE W;
	std::vector<TYPE> w, v;

	std::ifstream ifs("a.in");
	[&](std::istream& is) {
		is >> n >> W;
		w.resize(n);
		v.resize(n);
		for (int idx = 0; idx < n; ++idx) is >> v[idx] >> w[idx];
	} (std::cin);

	KnapsackProblem<TYPE> kp(n, W, w, v);
	kp.construct();
	std::cout << kp.getValue() << std::endl;
	//std::cerr << "node count   : " << kp.getCntNode() << std::endl;
	//std::cerr << "node visited : " << kp.getVisitedNode() << std::endl;

	/*std::mt19937 mt(0);
	std::uniform_int_distribution<int> rand(1, 9);

	while (true) {
		n = 5;
		W = rand(mt);
		w.resize(n);
		v.resize(n);
		for (int idx = 0; idx < n; ++idx) v[idx] = rand(mt), w[idx] = rand(mt);
		KnapsackProblem<TYPE> kp(n, W, w, v);

		magic = 1;
		kp.construct();
		TYPE x = kp.getValue();
		magic = 100;
		kp.construct();
		TYPE y = kp.getValue();
		if (x != y) {
			std::cout << "==============" << std::endl;
			std::cout << n << " " << W << std::endl;
			for (int i = 0; i < n; ++i) {
				std::cout << v[i] << " " << w[i] << std::endl;
			}
			std::cout << "--------------" << std::endl;
			std::cout << "     Correct value : " << y << std::endl;
			std::cout << "Experimental value : " << x << std::endl;
		}
	}*/
	return 0;
}


Measured memory_bytes: 42136