#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);
}