#include <cstdio>
#include <algorithm>

using namespace std;

int n, g, i, j, w[5001], p[10001], d1[10001], d2[10001];

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++)
    {
        for (j=1; j<=g; j++)
        {
            d2[j]=d1[j];
            if (w[i]<=j) d2[j]=max(d2[j], d1[j-w[i]]+p[i]);
        }
        for (j=1; j<=g; j++) d1[j]=d2[j];
    }
    printf ("%d", d2[g]);
}