#include <cstdio>
#define Nmax 5005
#define Gmax 10005

using namespace std;

int main() {
    int N, W, sol;
    int g[Nmax], p[Nmax];
    int i, j, v[Gmax];
    sol  = 0;
    v[0] = 0;

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

    scanf("%d %d", &N, &W);
    for (i = 1; i <= N; ++i)
        scanf("%d %d", &g[i], &p[i]);

    for (i = 1; i <= N; ++i) {
        for (j = W-g[i]; j >= 0; --j) {
            if (v[j+g[i] < v[j]+p[i]) {
                v[j+g[i] = v[j]+p[i];
                if (v[j+g[i]] > sol)
                    sol = v[j+g[i]];
            }
        }
    }

    printf("%d", sol);

    return 0;
}