#include <fstream>
#include <map>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int MAXIM = 5005;

int n, greutate_max;
int greutati[MAXIM];
int valori[MAXIM];

static inline void citire() {
    fin >> n >> greutate_max;
    for (int i = 0; i < n; ++i) {
        fin >> greutati[i] >> valori[i];
    }
}

map<pair<int, int>, int> cache; // cache[greu,k] = val


int rucsac(int greutate, int k) {
    if (greutate > greutate_max) {
        return -999999;
    }
    if (k == n) {
        return 0;
    }
    if (cache[{greutate, k}]) {
        return cache[{greutate, k}];
    }
    int optiunea_fara = rucsac(
        greutate,
        k + 1
    );
    int optiunea_cu = valori[k] + rucsac(
        greutate + greutati[k],
        k + 1
    );
    int raspuns = max(optiunea_fara, optiunea_cu);
    cache[{greutate, k}] = raspuns;
    return raspuns;
}

int main() {
    citire();
    fout << rucsac(0, 0) << '\n';
    return 0;
}