#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define NMAX 5000
#define GMAX 10000

int pmax = 0;

typedef pair<int, int> obiect; /// first = W; second=P
obiect ob[NMAX];
//int sumg[NMAX];
int n;
int g;

bool ord (const obiect& l, const obiect& r)
{
    return  (l.first*r.second<r.first*l.second);
}

/// S - indicele obiectului de la care incepem
int cont(const int s, int g_ramas) {
    if(g_ramas <= 0)
        return 0;
    if(s >= n)
        return 0;
    float t = 0;
    for(int i = s; (i < n)&&(g_ramas >= 1); i++) {
        if(g_ramas >= ob[i].first) {
            g_ramas -= ob[i].first;
            t += ob[i].second;
        } else {
            float g_part = float(ob[i].first)/float(g_ramas);
            float nv = ob[i].second*g_part;
            t += ceil(nv);
            g_ramas = 0;
        }
    }
    return ceil(t);
}

/// Lower bound
int greedy_lb() {
    int v = 0;
    int g_ramas = g;
    for(int i = 0; (i < n)&&(g_ramas > 0); i++) {
        if(g_ramas >= ob[i].first) {
            g_ramas -= ob[i].first;
            v += ob[i].second;
        }
    }

    return v;
}

void bkt(int i, int c, int s) {

    const int pfuture = cont(i, g - c);

    if(s + pfuture < pmax) {
        return;
    }

    /// Nu luam
    if(i + 1 < n) {
        bkt(i+1, c, s);
    }

    /// Luam
    const int nc = c + ob[i].first;
    const int ns = s + ob[i].second;
    if(nc <= g) {
        if(ns > pmax) {
            pmax = ns;
        }
        if(i + 1 < n) {
            bkt(i+1, nc, ns);
        }
    }
}

int main()
{
    FILE * fin = fopen("rucsac.in", "r");
    FILE * fout = fopen("rucsac.out", "w");
    fscanf(fin, "%d%d", &n, &g);
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d%d", &ob[i].first, &ob[i].second);
    }
    sort(ob, ob+n, ord);

    pmax = greedy_lb();

    bkt(0, 0, 0);
    fprintf(fout, "%d", pmax);
    fclose(fin);
    fclose(fout);
    return 0;
}