#include <stdio.h>
int v[2000];
int w[2000];

int max=0;
int maxval(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int maxsubset(int *v,int *w,int n,int s, int *wei)
{
    int cur1=0,cur2=0,ww1=0,ww2=0,maxi;

    //printf("#%d %d %d %d %d %d\n",cur1,cur2,ww1,ww2,s,n);
    if(n==1)
    {
        if(w[0]<=s)
        {
            *wei = w[0];
            return v[0];

        }
        else
        {
            *wei=0;
            return 0;
        }
    }

    cur1 = maxsubset(v,w,n-1,s,&ww1);
    //printf("!%d %d %d %d %d %d\n",cur1,cur2,ww1,ww2,s,n-1);
    cur2 = maxsubset(v,w,n-1,s-w[n-1],&ww2)+v[n-1];

    //printf("%d %d %d %d %d %d\n",cur1,cur2,ww1,ww2,s,n-1);

    if(ww1 <= s && ww2 + w[n-1] <= s)
    {

         maxi=maxval(cur1,cur2);

         if(maxi == cur1)
            *wei = ww1 + (*wei);
         else
            *wei = ww2 + w[n-1];

         //max = maxval(max,maxi);
         return maxi;
    }
    else if (ww1 > s)
    {
        if(ww2 + w[n-1] <= s)
        {
            *wei = ww2 + w[n-1];
            return cur2;
        }
        else
        {
            //*wei =0;
            return 0;
        }
    }
    else if (ww2 + w[n-1] > s)
    {
        if(ww1  <= s)
        {
            *wei = ww1 ;
            return cur1;
        }
        else
        {
            //*wei =0;
            return 0;
        }
    }
}
void main()
{
    int n,s,i,j,max=0,wei=0;


    scanf("%d %d",&n,&s);

    for(i=0;i<n;i++)
    {
        scanf("%d %d",&v[i],&w[i]);
    }

    j= maxsubset(v,w,n,s,&wei);

    //printf("max is %d weight %d\n",j,wei);
    printf("%d",j);
}