#include <stdio.h>

const int MAX_N = 5000, MAX_G = 10000;
const char *fi = "rucsac.in";
const char *fo = "rucsac.out";

int N,G, sol[MAX_N + 1][MAX_G + 1];

inline int MAX (int a, int b) { return (a > b) ? a : b; }

int main(int argc, const char * argv[]) {
    
    freopen (fi, "r", stdin);
    freopen (fo, "w", stdout);
    int w,p;
    scanf("%d%d",&N,&G);
    
    for (int i=1; i <= N; ++ i) {
        scanf("%d%d",&w,&p);
        
        for (int j = 1; j <= G; ++ j) {
            if (j < w)
                sol[i][j] = sol[i-1][j];
            else
                sol[i][j] = MAX (sol[i-1][j], sol[i-1][j - w] + p);
        }
        
    }
    
    printf("%d\n",sol[N][G]);
    return 0;
}