#include <cstdio>
#include <algorithm>

using namespace std;

int v[10010], a[5010], b[5010];

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

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

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

    for (int i = 1; i <= n; ++i)
        for (int j = g; j >= 0; --j)
            if (j >= a[i]) v[j] = max (v[j], v[j - a[i]] + b[i]);

    printf ("%d\n", v[g]);

    return 0;
}