#include <cstdio>
#include <algorithm>
using namespace std;

int n, G, i, j, l, w[5002], p[50002], d[2][10010];

int main ()
{

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

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

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

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

    printf("%d\n", d[l][G]);
    return 0;
}