#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]; // Sume partiale greutati
int sump[NMAX]; // Sume partiale pret
int n;
int g;

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

int range_pret(const int l, const int r) {
    int s = sump[r];
    if(l)
        s -= sump[l-1];
    return s;
}

int range_greutate(const int l, const int r) {
    int s = sumg[r];
    if(l)
        s -= sumg[l-1];
    return s;
}

int partial(const int o, const int g_ramas) {
    float g_part = float(ob[o].first)/float(g_ramas);
    float nv = ob[o].second*g_part;
    const int v = ceil(nv);
    return v;
}

// S - indicele obiectului de la care incepem
// upper bound
int cont_opt(const int s, int g_ramas) {
    if(g_ramas <= 0)
        return 0;
    if(s >= n)
        return 0;
    if(g_ramas <= ob[s].first) {
        return partial(s, g_ramas);
    }

    int l = s;
    int r = n - 1;
    int best = -1;

    while(l <= r) {
        const int m = (l + r)/2;
        const int x = range_greutate(s, m);
        if(x > g_ramas) {
            r = m - 1;
        } else {    // x <= g_ramas
            best = max(m, best);
            l = m + 1;
        }
    }

    g_ramas -= range_greutate(s, best);
    int v = range_pret(s, best);

    if((g_ramas > 0) && (best + 1 < n)) {
        v += partial(best+1, g_ramas);
    }
    return v;
}

// 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_opt(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);

    sumg[0] = ob[0].first;
    for(int i = 1; i < n; i++) {
        sumg[i] = sumg[i-1] + ob[i].first;
    }

    sump[0] = ob[0].second;
    for(int i = 1; i < n; i++) {
        sump[i] = sump[i-1] + ob[i].second;
    }

    pmax = greedy_lb();

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