#include<cstdio>
#include<algorithm>

using namespace std;

int n,gmax,G,g[5005],i,j,uz[10005][5005],profit[10005],c[5005],maxim,si,x;

int main(){

    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d%d",&n,&gmax);

    for(i=1;i<=n;++i){

        scanf("%d%d",&g[i],&c[i]);

    }
    for(G=1;G<=gmax;++G){
        for(i=1;i<=n;++i){
            if(g[i]<=G && uz[G-g[i]][i]==0)
                x=profit[G-g[i]]+c[i];
                if(x>maxim){
                    si=i;
                    profit[G]=x;
                    maxim=x;
                }
        }
        if(si){

            for(i=1;i<=n;++i)
            if(i!=si)
                uz[G][i]=uz[G-g[si]][i];
        }
            uz[G][si]=1;
            si=0;
            maxim=-1;
    }
    maxim=-1;
    for(i=1;i<=gmax;++i){

        if(profit[i]>maxim){
            maxim=profit[i];
            si=i;
        }
    }
    printf("%d\n",maxim);
       /* for(i=1;i<=n;++i){

            if(uz[si][i]==1){

            printf("%d\n",i);

            }

        }*/
    return 0;
}