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

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

 private:
    int N, K;
    vector<int> w;
    vector<int> p;

    void read_input() {
        ifstream fin("rucsac.in");
        cin >> N;
        cin >> K;

        w.push_back(0);
        p.push_back(0);

        for (int i = 0, e; i < N; i++) {
            cin >> e;
            w.push_back(e);

            cin >> e;
            p.push_back(e);
        }

        fin.close();
    }

    int rucsac(int N, int K, vector<int> w, vector<int> p) {
        vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));

        for (int i = 0; i < K + 1; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < K + 1; j++) {

                dp[i][j] = dp[i - 1][j];
    
                if (j - w[i] >= 0) {
                    int sol_aux = dp[i-1][j - w[i]] + p[i];

                    dp[i][j] = max(dp[i][j], sol_aux);
                }
            }
        }

        return dp[N][K];
    }

    int get_result() {
        return rucsac(N, K, w, p);
    }

    void print_output(int result) {
        ofstream fout("rucsac.out");

        cout << result;

        fout.close();
    }
};

int main() {
    auto* task = new (std::nothrow) Task{};  // hint: cppreference/nothrow

    if (!task) {
        std::cerr << "new failed\n";
        return -1;
    }

    task->solve();
    delete task;

    return 0;
}