#include <cstdio>
using namespace std;
int optim[10005],n,p,g[5005],v[5005],i,j;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&p);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&g[i],&v[i]);
    }
    optim[0]=0;
    int max1=0;
    for(i=1;i<=n;i++)
        for(j=p-g[i];j>=0;j--)
        {
            if(optim[j+g[i]]<optim[j]+v[i])
                optim[j+g[i]]=optim[j]+v[i];
            if(optim[j+g[i]]>max1) max1=optim[j+g[i]];
        }
    printf("%d",max1);
    return 0;
}