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


class Task { // T = O(n * g), S = O(g)
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int32_t n, g;
    vector<int32_t> weights;
    vector<int32_t> prices;

    void read_input() {
        ifstream fin("rucsac.in");
        fin.tie(0);
        
        fin >> n >> g;

        weights.resize(n + 1);
        prices.resize(n + 1);

        for (int i = 1; i <= n; i++) {
            fin >> weights[i] >> prices[i];
        }

        fin.close();
    }

    int get_result() {  
        vector<int> dp(g + 1, 0);

        for (int i = 1; i <= n; i++) {
            for (int cap = g; cap >= weights[i]; cap--) {
                dp[cap] = max(dp[cap], dp[cap - weights[i]] + prices[i]);
            }
        }

        return dp[g];
    }

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

        fout << result << "\n";
        fout.close();
    }
};

int main() {
    ios::sync_with_stdio(false);
    auto* task = new (nothrow) Task();

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

    task->solve();
    delete task;

    return 0;
}