#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX = 5001;
int n, G;
double best_profit = 0;
struct obiect
{
    int w, p;
    double raport;
    bool operator < (const obiect &other) const
    {
        return (raport > other.raport);
    }
};
obiect obiecte[NMAX];

double upperbound(int i, double crt_profit, double crt_weight)
{
    int capacity = G - crt_weight;
    double bound = crt_profit;
    while(i <= n && obiecte[i].w < capacity)
    {
        capacity -= obiecte[i].w;
        bound += obiecte[i].p;
        i++;
    }
    if(i <= n)
        bound += obiecte[i].p * ((double)capacity / obiecte[i].w);
    return bound;
}

void bkt(int i, double crt_profit, double crt_weight)
{
    if(i == n + 1)
    {
        best_profit = max(best_profit, crt_profit);
        return;
    }
    if(upperbound(i, crt_profit, crt_weight) <= best_profit)
        return;
    if(crt_weight + obiecte[i].w <= G)
        bkt(i + 1, crt_profit + obiecte[i].p, crt_weight + obiecte[i].w);
    bkt(i + 1, crt_profit, crt_weight);
}

int main()
{
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
    {
        fin >> obiecte[i].w >> obiecte[i].p;
        obiecte[i].raport = (obiecte[i].w == 0 ? 1e9 : (double)obiecte[i].p / obiecte[i].w);
    }
    sort(obiecte + 1, obiecte + n + 1);
    bkt(1, 0, 0);
    fout << (int)best_profit;

    fin.close();
    fout.close();
    return 0;
}