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

void set_io(string name = "")
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

int main()
{
    set_io("rucsac");

    int num_objs;
    int max_weight;
    cin >> num_objs;
    cin >> max_weight;

    int profit_index = 0;
    vector<int> profit_matrix[2];
    profit_matrix[0].resize(max_weight + 1, 0);
    profit_matrix[1].resize(max_weight + 1, 0);

    for (int i = 0; i < num_objs; i++) {
        int weight;
        int profit;
        cin >> weight;
        cin >> profit;

        auto &curr_matrix = profit_matrix[profit_index];
        auto &next_matrix = profit_matrix[1 - profit_index];
        profit_index = 1 - profit_index;

        for (int w = 1; w <= max_weight; w++) {
            next_matrix[w] =
                max(curr_matrix[w],
                    (w < weight) ? 0 : curr_matrix[w - weight] + profit);
        }
    }

    cout << profit_matrix[profit_index][max_weight] << '\n';

    return 0;
}