#include <bits/stdc++.h>
using namespace std;

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

const int MAX_WEIGHT = 5e3;
const int MAX_OBJECTS = 1e4;

int n, g;
int w[MAX_OBJECTS + 1], p[MAX_OBJECTS + 1];
vector<vector<int>> maxProfit(MAX_WEIGHT, vector<int>(MAX_OBJECTS, -1));
int answer;

int solve(int weight, int index) {
    if (index > n || weight > g) {
        return 0;
    }
    if (maxProfit[weight][index] != -1) {
        return maxProfit[weight][index];
    }
    int profit = solve(weight, index + 1), currentProfit = 0, newWeight = weight + w[index];
    if (newWeight <= g) {
        currentProfit = p[index] + solve(newWeight, index + 1);
    }
    maxProfit[weight][index] = max(profit, currentProfit);
    return maxProfit[weight][index];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fin >> n >> g;
    for (int i = 1; i <= n; ++i) {
        fin >> w[i] >> p[i];
    }
    cout << solve(0, 0);
    return 0;
}