#include <bits/stdc++.h>

using namespace std;


int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, g;
    cin >> n >> g;
    vector<pair<int, int>>a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end(), [&] (const pair<int, int>&L, const pair<int, int>&R) {
        return (long double)L.second / L.first > (long double)R.second / R.first;
    });

    auto at_most = [&] (int pos, int rem) {
        double res = 0;
        for(int i = pos; i < n; ++i) {
            if(rem - a[i].first >= 0) rem -= a[i].first, res += a[i].second;
            else {
                double take = (double)rem / a[i].first;
                res += take * a[i].second;
                break;
            }
        }
        return (int)res + 1;
    };
    int global_max = -1;
    function<void(int, int, int)>bkt = [&] (int pos, int rem, int got) {
        if(pos == n) {
            global_max = max(global_max, got);
            return;
        }


        if(rem - a[pos].first >= 0 && got + at_most(pos + 1, rem - a[pos].first) + a[pos].second > global_max)
            bkt(pos + 1, rem - a[pos].first, got + a[pos].second);
        if(got + at_most(pos + 1, rem) > global_max)
            bkt(pos + 1, rem, got);

    };

    bkt(0, g, 0);
    cout << global_max;
}