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

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

struct Obiect {
    int profit, greutate;
};

int maxProfit;
int N, G;
Obiect obiecte[10000];

// Funcția de backtracking
void knapsackBacktrack(int index, int currentProfit, int currentWeight) {
    // Dacă am depășit greutatea maximă, nu continuăm
    if (currentWeight > G) {
        return;
    }

    // Actualizăm profitul maxim dacă e cazul
    if (currentProfit > maxProfit) {
        maxProfit = currentProfit;
    }

    // Dacă am procesat toate obiectele, ne oprim
    if (index == N) {
        return;
    }

    // Alegem să nu includem obiectul curent
    knapsackBacktrack(index + 1, currentProfit, currentWeight);

    // Alegem să includem obiectul curent
    knapsackBacktrack(index + 1, currentProfit + obiecte[index].profit, currentWeight + obiecte[index].greutate);
}

int main() {
    f >> N >> G;

    for (int i = 0; i < N; i++) {
        f >> obiecte[i].greutate >> obiecte[i].profit;
    }

    maxProfit = 0;
    knapsackBacktrack(0, 0, 0);

    g<< maxProfit << endl;

    return 0;
}