#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(g_ramas)/float(ob[i].first);
            float nv = ob[i].second*g_part;
            t += 1+ceil(nv);
            g_ramas = 0;
        }
    }
    return ceil(t);
}

void bkt(int i, int c, int s) {
    if(c >= g || i >= n)
        return;

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

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

    if(s > pmax) {
        pmax = s;
    }

    if(i + 1 <= n) {
        bkt(i+1, c + ob[i].first, s + ob[i].second);
        bkt(i+1, c, s);
    }
}

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 = 0;

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