#include <cstdio>
#define NMAX 50001
#define GMAX 10001
using namespace std;

int n, g, p[NMAX], w[NMAX];
int m[NMAX][GMAX];

int max(int a, int b) {
    if (a < b) {
        return b;
    }
    return a;
}

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

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= g; ++j) {
            if (w[i] <= j) {
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + p[i]);
            } else {
                m[i][j] = m[i-1][j];
            }
        }
    }

    printf("%d \n", m[n][g]);

    return 0;
}