#include <cstdio>
#include <iostream>
using namespace std;
int n,v[5002],gc,vc,gmax,h,k,vmax,smax[5002],maxg,s[5002],g[5002];
void afis()
{
    int i;
    printf("%d\n",vmax);
}
void ruc(int i)
{
    int j;
    for(j=0;j<=1;j++)
    {
        if(gc+j*g[i]<=gmax)
        {
            s[i]=j;
            gc+=g[i]*j;
            vc+=v[i]*j;
            if(vc>vmax)
            {
                vmax=vc;
                for(k=1;k<=i;k++)smax[k]=s[k];
                maxg=gc;
                h=i;
            }
            if(i<n)ruc(i+1);
            gc-=j*g[i];
            vc-=j*v[i];
        }
    }
}
int main()
{
    int i;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&gmax);
    for(i=1;i<=n;i++)scanf("%d%d",&g[i],&v[i]);
    i=1;
    ruc(i);
    afis();
    return 0;
}