#include <fstream>

using namespace std;

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

// 1 ≤ N ≤ 5000
// 1 ≤ G ≤ 10000
// 0 ≤ Wi, Pi ≤ 10000

const int MAX_N = 5005;
const int MAX_G = 10005; 

struct t_obiect {
    int weight;
    int val;
};

int memo[MAX_N][MAX_G];

int knapscak(int n, int capacity, t_obiect objects[]) {
    if (n == -1) {
        return 0;
    }

    if (capacity == 0) {
        return 0;
    }

    if (memo[n][capacity] != 0) {
        return memo[n][capacity];
    }

    if (objects[n].weight > capacity) {
        return knapscak(n - 1, capacity, objects);
    }

    int obj_val = objects[n].val;
    int obj_weight = objects[n].weight;

    int temp1 = knapscak(n - 1, capacity, objects);
    int temp2 = obj_val + knapscak(n - 1, capacity - obj_weight, objects);

    int sol = max(temp1, temp2);
    memo[n][capacity] = sol;

    return sol;
}

int main() {

    int nr_elem;
    int weight;
    t_obiect objects[MAX_N];

    fin >> nr_elem >> weight;

    for (int i = 0; i < nr_elem; i++) {
        int weight;
        int val;

        fin >> weight;
        fin >> val;

        t_obiect ob = {weight, val};
        objects[i] = ob;
    }

    fout << knapscak(nr_elem - 1, weight, objects);

    return 0;
}