#include <iostream>
#include <fstream>

using namespace std;

const int maxn = 10005;

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

int n, g;
int profit[maxn];
int greutate[maxn];
long long profitMax;
int arr[maxn][maxn];

void bt(int pos, long long gr, long long pr) {
    if (pos == n) {
        if (pr > profitMax)
            profitMax = pr;
        return;
    }
    if (arr[pos][gr] > pr) return;
    else arr[pos][gr] = pr;
    if (gr + greutate[pos] <= g)
        bt(pos + 1, gr + greutate[pos], pr + profit[pos]);
    bt(pos + 1, gr, pr);
}

int main() {
    in >> n >> g;
    for (int i = 0; i < n; ++i)
        in >> greutate[i] >> profit[i];

    bt(0, 0, 0);
    out << profitMax;
    return 0;
}