#include <stdio.h>
#include <stdlib.h>

#define IN "rucsac.in"
#define OUT "rucsac.out"
#define NMAX 5001
#define CMAX 10001

int cost1[CMAX], cost2[CMAX];

struct OBJECT{
    int w, p;
};

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

int best (int n, int g, struct OBJECT object[]){
    int i, cw;

    for (i = 1; i <= n; ++ i){
        for (cw = 1; cw <= g; ++ cw){
            cost2 [cw] = cost1 [cw];
            if (cw >= object[i].w)
                cost2 [cw] = max (cost1 [cw], cost1 [cw - object[i].w] + object[i].p);
        }
        for (cw = 1; cw <= g; ++ cw)
            cost1 [cw] = cost2 [cw];
    }

    return cost1[g];
}

int main()
{
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    int n, g, i;
    struct OBJECT object[NMAX];

    scanf ("%d", &n);
    scanf ("%d", &g);

    for (i = 1; i <= n; ++i)
        scanf ("%d%d", &object[i].w, &object[i].p);

    printf ("%d\n", best (n, g, object));

    fclose (stdin);
    fclose (stdout);
    return 0;
}