#include <cstdio>

#define NMAX 5001
#define GMAX 10001
#define INF (1 << 30)

using namespace std;

int n;
int g;
int s[GMAX];
int w[NMAX];
int p[NMAX];

void read()
{
    freopen("rucsac.in", "r", stdin);

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

int solve()
{
    int maxim = -INF;

    for(int i = 1; i <= n; ++ i)
        for(int j = g - w[i]; j >= 0; -- j)
            if(s[j + w[i]] < s[j] + p[i])
            {
                s[j + w[i]] = s[j] + p[i];

                if(s[j + w[i]] > maxim)
                    maxim = s[j + w[i]];
            }

    return maxim;
}

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

    read();
    printf("%d\n", solve());

    return 0;
}