#include <iostream>

#define NMax 5005
#define WMax 10005

using namespace std;

int N, G, W[NMax], P[NMax], DP[2][WMax];

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

void Read ()
{
    freopen ("rucsac.in", "r", stdin);
    scanf ("%d %d", &N, &G);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &W[i], &P[i]);
    }
}

void Print ()
{
    freopen ("rucsac.out", "w", stdout);
    printf ("%d\n", DP[0][G]);
}

int main()
{
    Read ();
    for (int i=1; i<=N; ++i)
    {
        for (int w=0; w<=G; ++w)
        {
            DP[1][w]=DP[0][w];
            if (w-W[i]>=0)
            {
                DP[1][w]=Max (DP[1][w], DP[0][w-W[i]]+P[i]);
            }
        }
        for (int w=0; w<=G; ++w)
        {
            DP[0][w]=DP[1][w];
            DP[1][w]=0;
        }
    }
    Print ();
    return 0;
}