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

#define LMAX 5000

int N,G;
int v[LMAX], g[LMAX], s[LMAX];
vector<int> u[LMAX];

void citire() {
    scanf("%d %d", &N, &G);
    for (int i=1; i<=N; ++i)
        scanf("%d %d", &g[i], &v[i]);
    for (int i=1; i<=G; ++i)
        s[i] = -1;
}

void util(int l, int e) {
    int f = l-g[e];
    u[l].assign(u[f].begin(), u[f].end());
    u[l].push_back(e);
}

void rucsac() {
    for (int e=1; e<=N; ++e)
        for (int i=G; i>=0; --i)
            if (i-g[e]>=0 && s[i-g[e]]>=0) {
                if (s[i-g[e]] + v[e]>s[i]) {
                    s[i] = s[i-g[e]] + v[e];
                    //util(i,e);
                }
            }

    int max=s[G];
    for (int i=G-1; i>=0; --i)
        if (s[i]>max) max = s[i];
    printf("%d", max);
}

int main () {

    freopen("rucsac.in","rt",stdin);
    freopen("rucsac.out","wt",stdout);

    citire();
    rucsac();

    return 0;
}