#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <random>

using namespace std;

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

int n, maxWeight;
int maxProfit = -1;
vector<pair<int, int>> backpack;

const int GMAX = 10010;
const int NMAX = 5001;

// (3, 1) => 5;
// (greutate totala, indicele ultimului obiect selectat) -> stare

void backtracking(int lastIndex , int sumWeight , int sumProfit, int mat[NMAX][GMAX]) {
    if (sumWeight > maxWeight) {
        return;
    }
    if (mat[lastIndex][sumWeight] != -1 && mat[lastIndex][sumWeight] >= sumProfit) {
        return;
    }
    mat[lastIndex][sumWeight] = sumProfit;

    maxProfit = max(maxProfit, sumProfit);

    for (int i = lastIndex; i < backpack.size(); ++i) {
        backtracking(i + 1, sumWeight + backpack[i].first, sumProfit + backpack[i].second, mat);
    }
}


int main() {
    fin >> n >> maxWeight;
    int mat[n + 1][GMAX];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < maxWeight; ++j) {
            mat[i][j] = -1;
        }
    }

    for (int i = 0; i < n; ++i) {
        int weight, profit;
        fin >> weight >> profit;
        backpack.emplace_back(weight, profit);
    }

    backtracking(0, 0, 0, mat);

    fout << maxProfit;

    return 0;
}
/*
6 10
3 7
3 4
1 2
1 9
2 4
1 5
 */