#include <cstdio>
#include <algorithm>

using namespace std;
FILE* FIN=freopen("rucsac.in","r",stdin);
FILE* FOUT=freopen("rucsac.out","w",stdout);

int n,g,mx;
struct i3
{
    int m,p,r;
}v[5120];

void cit()
{
    int i;
    scanf("%d%d",&n,&g);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&v[i].m,&v[i].p);
        v[i].r=v[i].p/v[i].m;
    }
}
char cmp(i3 x,i3 y)
{
    return x.r>y.r;
}
void tst(int x)
{
    if(x>mx)
        mx=x;
}
void backt(int l,int s,int sol)
{
    int i;
    if(l==n)
    {
        tst(sol);
        return;
    }
    if(s==g)
    {
        tst(sol);
        return;
    }
    backt(l+1,s,sol);
    if(s+v[l].m<=g)
        backt(l+1,s+v[l].m,sol+v[l].p);
    return;
}
void af()
{
    printf("%d",mx);
}
int main()
{
    cit();
    backt(0,0,0);
    af();
    return 0;
}