#include<stdio.h>
#define NMAX 5001
#define GMAX 10001

using namespace std;

int mat[3][GMAX];
int G[NMAX],C[NMAX];

int main(){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,line=0;
    scanf("%d %d",&n,&g);
    for(int i=1;i<=n;++i)
        scanf("%d %d",&G[i],&C[i]);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=g;++j){
            mat[1-line][j]=mat[line][j];
            if(G[i]<=j)
                if(C[i]+mat[line][j-G[i]]>mat[1-line][j])
                    mat[1-line][j]=C[i]+mat[line][j-G[i]];
                else
                    mat[1-line][j]=mat[1-line][j];
        }
        line=1-line;
    }
    printf("%d\n",mat[line][g]);
    return 0;
}