#include <cstdio>
#define Gmax 10005
#define Nmax 5005

using namespace std;

inline int max(int a, int b) {
    if (a > b) {
        return a;
    }

    return b;
}

int main() {
    int i, cw, N, G, l;
    int D[2][Gmax];
    int w[Nmax], p[Nmax];

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf("%d%d", &N, &G);
    for (i = 1; i <= N; ++i)
        scanf("%d%d", &w[i], &p[i]);

    for (i = 1, l = 0; i <= N; ++i, l = 1-l) {
        for (cw = 0; cw <= G; ++cw) {
            D[1-l][cw] = D[l][cw];

            if (cw >= w[i]) {
                D[1-l][cw] = max(D[l][cw], D[l][cw-w[i]] + p[i]);
            }
        }
    }

    printf("%d", D[l][G]);

    return 0;
}