#include<bits/stdc++.h>
#define debug cerr<<"OK";

using namespace std;

#define MAXN 5010
#define MAXG 10010

int v[MAXG], a[MAXN], b[MAXN];

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;
}