#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

struct Knapsack {
    struct Object {
        int price;
        int weight;

        Object() : price(0), weight(0) {
        }

        Object(const int _price, const int _weight) : price(_price), weight(_weight) {
        }
    };

    vector<Object> v;
    int capacity;

    Knapsack(const int _capacity) : capacity(_capacity) {
    }

    void EmplaceItem(const int price, const int weight) {
        v.emplace_back(Object(price, weight));
    }

    int Compute(const int& a, const int& b, const int& c, const int& d) const {
        return a * d - b * c;
    }

    int BranchAndBound(int price, int weight, int m_front, int m_back) {
        int ret = 0;
        if (weight <= capacity) {
            if (price > ret) {
                ret = price;
            }
            while (m_back < SZ(v) and Compute(price - ret - 1, weight - capacity, v[m_back].price, v[m_back].weight) >= 0) {
                ret = max(ret, BranchAndBound(price + v[m_back].price, weight + v[m_back].weight, m_front, m_back + 1));
                m_back += 1;
            }
        } else {
            while (m_front >= 0 and Compute(price - ret - 1, weight - capacity, v[m_front].price, v[m_front].weight) >= 0) {
                ret = max(ret, BranchAndBound(price - v[m_front].price, weight - v[m_front].weight, m_front - 1, m_back));
                m_front -= 1;
            }
        }
        return ret;
    }

    int Solve() {
        sort(v.begin(), v.end(), [](const Object &A, const Object &B) {
            return A.price * B.weight > A.weight * B.price;
        });
        int totalPrice = 0, totalWeight = 0;
        int lastUsed = 0;
        while (lastUsed < SZ(v) and totalWeight <= capacity) {
            totalPrice += v[lastUsed].price;
            totalWeight += v[lastUsed].weight;
            lastUsed += 1;
        }
        return BranchAndBound(totalPrice, totalWeight, lastUsed - 1, lastUsed);
    }
};

int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int capacity, n; cin >> n >> capacity; 
    
    Knapsack task_solver(capacity);
    for (int i = 0; i < n; i += 1) {
        int weight, price; cin >> weight >> price;
        task_solver.EmplaceItem(price, weight);
    }
    cout << task_solver.Solve() << '\n';

    return 0;
}