#include <cstdio>
using namespace std;

int n,gr,g[5005],p[5005];
int linie1[10005],linie2[10005];


void citire(){
    scanf("%d %d",&n,&gr);
    for(int i=1;i<=n;++i)
        scanf("%d %d",&g[i],&p[i]);
}

void atribuire(){
    for(int i=0;i<=gr;++i)
        linie1[i]=linie2[i];
}

void rezolvare(){
    for(int i=1;i<=n;++i){
        for(int j=0;j<=gr;++j){
            linie2[j]=linie1[j];
            if(g[i]<=j)
                if(linie2[j]<linie1[j-g[i]]+p[i])
                    linie2[j]=linie1[j-g[i]]+p[i];
        }
        atribuire();
    }
    printf("%d",linie1[gr]);
}

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    citire();
    rezolvare();
    return 0;
}