#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
int n, G, v[5005], g[5005], maxx=0, ver[5005];
void rec(int x, int greu, int prof)
{
    if(greu>G)
    {
        return;
    }

    if(prof>maxx)
        maxx=prof;

    if(x==n+1)
    {
        return;
    }

    ver[x]=1;
    rec(x+1, greu+g[x], prof+v[x]);
    ver[x]=0;
    rec(x+1, greu, prof);
    return;
}
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    cin>>n>>G;
    for(int i=1; i<=n; i++)
    {
        cin>>g[i]>>v[i];
    }
    rec(1, 0, 0);
    cout<<maxx;
    return 0;
}