#include<stdio.h>
int g[5001],c[5001],s[10001],r[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(s[g[1]]=c[1],i=2;i<=n;i++) {
		for(j=1;j<=m;j++)
            r[j]=s[j];
       	if(r[g[i]]<c[i])
            s[g[i]]=c[i];
       	for(j=1;j<=m-g[i];j++)
       	if(r[j+g[i]]<r[j]+c[i])
            s[j+g[i]]=r[j]+c[i];
	}
	for(t=s[1],i=2;i<=m;i++)
		t=t<s[i]?s[i]:t;
	printf("%d",t);
}