// SPDX-License-Identifier: BSD-3-Clause

#include <algorithm> // max
#include <fstream> // ifstream, ofstream
#include <iostream> // cin, cout, cerr
#include <memory> // unique_ptr pentru Task
#include <vector> // vector
using namespace std;

class Task {
public:
    void solve() {
        read_input();
        write_output(get_result());
    }

private:
    int n, W;
    vector<int> w, p;

    void read_input() {
        ifstream fin("rucsac.in");
        // citeste datele
        fin >> n >> W;
        p.resize(n + 1); // redimensioneaza v sa aiba n elememnte
        w.resize(n + 1); // redimensioneaza v sa aiba n elememnte
        for (int i = 1; i <= n; ++i) {
            fin >> w[i] >> p[i];
        }
        fin.close();
    }

    int get_result() {
        // dp este o matrice de dimensiune (n + 1)x(W+1)
        // pentru ca folosim dp[0][*] pentru multimea vida
        //                   dp[*][0] pentru situatia in care ghiozdanul are capacitate 0
        vector<vector<int>> dp(n + 1);
        for (int i = 0; i <= n; ++i) {
            dp[i].resize(W + 1);
        }

        // cazul de baza
        for (int cap = 0; cap <= W; ++cap) {
            dp[0][cap] = 0;
        }

        // cazul general
        for (int i = 1; i <= n; ++i) {
            for (int cap = 0; cap <= W; ++cap) {
                // nu folosesc obiectu i => e solutia de la pasul i - 1
                dp[i][cap] = dp[i - 1][cap];

                // folosesc obiectul i, deci trebuie sa rezerv w[i] unitati in rucsac
                // inseamna ca inainte trebuie sa ocup maxim cap - w[i] unitati
                if (cap - w[i] >= 0) {
                    int sol_aux = dp[i - 1][cap - w[i]] + p[i];
                    dp[i][cap] = max(dp[i][cap], sol_aux);
                }
            }
        }
        return dp[n][W];
    }

    void write_output(int result) {
        ofstream fout("rucsac.out");
        fout << result << "\n";
        fout.close();
    }
};

// [ATENTIE] NU modifica functia main!
int main() {
    std::unique_ptr<Task> task {new (nothrow) Task()};
    if (!task) {
        std::cerr << "new failed: WTF are you doing? Throw your PC!\n";
        return -1;
    }
    task->solve();
    return 0;
}