#include <iostream>
#include <vector>

int getMaxProfit(int n, int weight, std::vector<int> &w, std::vector<int> &p) {
    std::vector<int> dp(weight + 1, 0); //n * weight
    for (int i = 1; i <= n; ++i) {
        std::vector<int> copy(dp);
        for (int j = 0; j <= weight; ++j) {
            if (w[i] <= j) {
                dp[j] = std::max(copy[j], copy[j - w[i]] + p[i]);
            }
        }

    }
    return dp[weight];
}

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("ruccsac.out", "w", stdout);
    int n, weight;
    std::cin >> n >> weight;
    std::vector<int> w(n + 1), p(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> w[i] >> p[i];
    }
    std::cout << getMaxProfit(n, weight, w, p);
    return 0;
}