#include <fstream>
#include <vector>

using namespace std;

struct Object {
    int weight;
    int profit;
};

int Solve(const vector<Object>& vec, int cap) {
    vector<vector<int>> dp(2, vector<int>(cap + 1, 0));
    for (size_t i = 0; i < vec.size(); i += 1) {
        auto& curr = dp[i % 2];
        const auto& prev = dp[1 - i % 2];

        for (int w = 0; w <= cap; w += 1) {
            curr[w] = max(
                // Nu luam obiectul.
                prev[w],
                // Luam obiectul, daca putem.
                vec[i].weight <= w ? (prev[w - vec[i].weight] + vec[i].profit)
                                   : 0
            );
        }
    }
    return dp[1 - vec.size() % 2].back();
}

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

    int n, cap;
    fin >> n >> cap;

    vector<Object> vec(n);
    for (auto& obj : vec) {
        fin >> obj.weight >> obj.profit;
    }

    auto res = Solve(vec, cap);
    fout << res << "\n";
    return 0;
}