#include<stdio.h>
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];
				if(s[j+g[i]]>t)
					t=s[j+g[i]];
        	}
    printf("%d",t);
}