#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
pair<int,int> S1[10001],S2[10001],N[10001],*V,*C,*A;
int n,LV,LN,LC,G,i,j,k,g,P,p;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    V=S1;C=S2;
    scanf("%d%d",&n,&G);
    LV=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&g,&p);
        for(LN=0;V[LN].first+g<=G&&LN<LV;LN++)
            N[LN]=make_pair(V[LN].first+g,V[LN].second+p);
        for(j=0,k=0,LC=0;j<LV&&k<LN;)
        {
            if(V[j].first<N[k].first) C[LC++]=V[j++];
            else if(V[j].first>N[k].first) C[LC++]=N[k++];
            else
            {
                if(V[j].second>N[k].second) C[LC++]=V[j];
                else C[LC++]=N[k];
                j++;k++;
            }
        }
        for(;j<LV;j++) C[LC++]=V[j];
        for(;k<LN;k++) C[LC++]=N[k];
        A=V;V=C;C=A;LV=LC;
    }
    for(i=0;i<LV;i++) P=max(P,V[i].second);
    printf("%d\n",P);
    return 0;
}