#include <fstream>
#include <algorithm>
// #include <iostream>

#define MAX 5000
#define GMAX 1000

using namespace std;

ifstream cin ("rucsac.in");
ofstream cout("rucsac.out");

struct obiect
{
    int val;
    int greutate;
    bool operator < (const obiect & obj) const 
    {
        float raport1 = 1.0 * this->val / this->greutate;
        float raport2 = 1.0 * obj.val / obj.greutate;
        if(raport1 != raport2)
            return raport1 > raport2;
        return this->val > obj.val;
    }
};

int n, G;
int best;
obiect v[MAX+5];

void bkt(int g, int lastIndex, int cost)
{
    if(cost > best)
        best = cost;
    if(lastIndex > n)
        return;
    int g2 = g;
    int sum = 0;

    for(int i = lastIndex + 1;i <= n; i++)
        if(g2 + v[i].greutate <= G)
            sum += v[i].val, g2 += v[i].greutate;
        else {
            sum += v[i].val * (G-g2) / v[i].greutate;
            break;
        }
    if(sum + cost < best)
        return;
                
    for(int i = lastIndex+1;i <= n; i++) 
    {
        if(g+v[i].greutate <= G)
            bkt(g+v[i].greutate, i, cost + v[i].val);
    }
}

int main()
{
    cin >> n >> G;
    for(int i = 1;i <= n; i++)
        cin >> v[i].greutate >> v[i].val;
    
    std::sort(v+1,v+1+n);

    int g2 = 0;
    for(int i = 1;i <= n; i++)
        if(g2 + v[i].greutate <= G)
            best += v[i].val, g2 += v[i].greutate;

    bkt(0, 0, 0);
    cout << best;
}