#include <cstdio>
#define max(a, b) a >= b ? a : b

using namespace std;

int n, g, l, pmx, w[5005], p[5005], d[2][10005];

int main()
{
    FILE *in, *out;
    in = freopen("rucsac.in", "r", stdin);
    out = freopen("rucsac.out", "w", stdout);

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

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

    fclose(in);

    for (int i = 1; i <= n; ++i, l = 1 - l)
        for (int cw = 0; cw <= g; ++cw) {
            d[1 - l][cw] = d[l][cw];
            if (w[i] <= cw)
                d[1 - l][cw] = max(d[1 - l][cw], d[l][cw - w[i]] + p[i]);
        }

    pmx = d[l][g];

    printf("%d", pmx);
    fclose(out);

    return 0;
}