#include <fstream>
#include <algorithm>
// #include <iostream>

#define MAX 5000
#define GMAX 1000

using namespace std;

ifstream cin ("rucsac.in");
ofstream cout("rucsac.out");

struct obiect
{
    int val;
    int greutate;
    bool operator < (const obiect & obj) const 
    {
        return 1.0 * this->val / this->greutate > 1.0 * obj.val / obj.greutate;
    }
};

int dp[MAX+1][GMAX+1], n, G, best;
obiect v[MAX+5];

void bkt(int g, int lastIndex, int cost)
{
    if(cost > best)
        best = cost;
    if(lastIndex > n)
        return;
    for(int i = lastIndex+1;i <= n && g + v[i].greutate <= G; i++) {
         bkt(g+v[i].greutate, i, cost + v[i].val);
    }
}

int main()
{
    cin >> n >> G;
    for(int i = 1;i <= n; i++)
        cin >> v[i].greutate >> v[i].val;
    std::sort(v+1,v+1+n);
    bkt(0, 0, 0);
    cout << best;
}