#include<cstdio>
int g[5001],c[5001],s[10001],m,n,i,j,t;
int main()
{
    freopen("rucsac.in","r",stdin),freopen("rucsac.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d%d",g+i,c+i);
    for(i=1;i<=n;i++)
        for(j=m-g[i];j>=0;j--)
        	if(s[j+g[i]]<s[j]+c[i])
            	s[j+g[i]]=s[j]+c[i],t=s[j+g[i]]>t?s[j+g[i]]:t;
    printf("%d",t);
}