#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, bestv;
int bestx[N], pos[N];

// 物品节点
struct nodep
{
    int id;
    int w, v;
    bool operator < (const nodep& t ) const
    {
        return v*1.0 / w > t.v*1.0 / t.w;
    }
}item[N];

// 优先队列里面的扩展节点
struct node
{
    int level;// 层次数
    int cw, cv, ub;
    node * pa;
    bool Lchild;
    // 构造函数
    node () { }
    node (int cw, int cv, int level, node* pa, bool Lchild)
    {
        this->cv = cv, this->cw = cw, this->level = level;
        this->pa = pa, this->Lchild = Lchild;
    }
};

// 比较结构体，用于优先队列里的指针元素比较优先级
struct cmp
{
    bool operator() (const node* a, node* b)
    {
        return a->ub < b->ub;
    }
};

// 上界函数
int bound(node* t)
{
    int d = t->level;
    int cw = t->cw;
    int cv = t->cv;
    for(int i = d + 1; i <= n; i ++)
    {
        if(cw + item[i].w <= m)
        {
            cv += item[i].v;
            cw += item[i].w;
        }
        else
        {
            cv += item[i].v*1.0 / item[i].w * (m - cw);
            break;
        }
    }
    return cv;
}
int main()
{

    cin >> n >> m;
    for(int i = 1; i <= n; i ++) 
    {
        cin >> item[i].w >> item[i].v;
        item[i].id = i;
    }
    // 按照物品的性价比排序
    sort(item + 1, item + n + 1);

    priority_queue<node*, vector<node*>, cmp> q;
    // 创建根节点
    node *t = new node(0, 0, 0, NULL, -1);
    t->ub = bound(t);
    q.push(t);

    // 分支限界
    while(q.size())
    {
        // 取出父节点
        node* fa = (q.top());
        q.pop();
        // 要扩展的子节点的层数
        int d = fa->level + 1;
        // 到达叶子节点结束搜索，计算最优解
        if(d > n)
        {
            bestv = fa->cv;
            node* p = fa;
            // 构造最优解
            while(p != NULL)
            {
                bestx[item[p->level].id] = p->Lchild;
                p = p -> pa;
            }
            break;
        }
        // 扩展左孩子
        if(fa->cw + item[d].w <= m)
        {
            node* ld = new node (fa->cw + item[d].w, fa->cv + item[d].v, d, fa, 1);
            ld->ub = bound(ld);
            q.push(ld);
            // 更新最优解
            if(ld->cv > bestv)
            {
                bestv = ld->cv;
            }
        }
        // 扩展右孩子
        node* rd = new node (fa->cw, fa->cv, d, fa, 0);
        rd->ub = bound(rd);

        // 上界函数剪枝
        if(rd->ub >= bestv)
        {
            q.push(rd);
        }
    }
    cout << bestv << endl;
    // for(int i = 1; i <= n; i ++)
    // {
    //     if(i != n) cout << bestx[i] << " ";
    //     else cout << bestx[i];
    // }
    return 0;
}