#include <cstdio>
using namespace std;

int n,gr,g[5005],p[5005];
int matrice[5005][10005];


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

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

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