#include <cstdio>
#include <iostream>

#define NMAX 5001
#define GMAX 10001

using namespace std;

typedef struct {
    int weight, value;
} THING;

bool used[NMAX];
int n, W, cache[NMAX][GMAX];
THING things[NMAX];

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

    cin >> n >> W;
    for (int it = 1; it <= n; ++it) {
        cin >> things[it].weight >> things[it].value;
    }

    for (int it = 1; it <= n; ++it) {
        for (int g = things[it].weight; g <= W; ++g) {
            cache[it][g] = max(cache[it][g], cache[it - 1][g]);
            cache[it][g] = max(cache[it][g], cache[it - 1][g - things[it].weight] + things[it].value);
        }
    }

    cout << cache[n][W];

    return 0;
}