#include <cstdio>
using namespace std;

const int NMAX = 5004, GMAX = 10004;
int W[NMAX], P[NMAX], D[2][GMAX];

int main () {

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

    int N, G, i, j;
    bool c = 1;
    scanf ("%d%d", &N, &G);

    for (i = 1; i <= N; ++i)
        scanf ("%d%d", &P[i], &W[i]);

    for (i = 1; i <= N; ++i) {
        c = !c;
        for (j = 0; j <= G; ++j) {
            D[c][j] = D[!c][j];
            if (j >= W[i] && D[!c][j - W[i]] + P[i] > D[c][j])
                D[c][j] = D[!c][j - W[i]] + P[i];
        }
    }

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

}