#include <stdio.h>

using namespace std;

int gg[10005],gr[5005],pr[5005];
char s[10005];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,i,j,pmax=0;
    s[0]=1;
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",gr+i,pr+i);
    }
    for(i=1;i<=n;i++)
    {
        for(j=g-gr[i];j>=0;j--)
        {
            if(s[j]&&gg[j+gr[i]]<gg[j]+pr[i])
            {
                s[j+gr[i]]=1;
                gg[j+gr[i]]=gg[j]+pr[i];
                if(pmax<gg[j]+pr[i]) pmax=gg[j]+pr[i];
            }
        }
    }
    printf("%d",pmax);

    return 0;
}