#include <cstdio>

#define MAX(a,b) (a<b)?b:a

int N,G;
int M[5010][10010];

int main () {

    int w, v;

    freopen("rucsac.in","rt",stdin);
    freopen("rucsac.out","wt",stdout);

    scanf("%d %d", &N, &G);
    for (int i=1; i<=N; ++i) {
        scanf("%d %d", &w, &v);
        for (int j=1; j<=G; ++j)
            if (j>=w) M[i][j] = MAX(M[i-1][j], M[i-1][j-w] + v);
            else M[i][j] = M[i-1][j];
    }

    printf("%d", M[N][G]);
    return 0;
}