#include <bits/stdc++.h>

using namespace std;

class solution {
public:

int N, G;
vector<pair<int, int>> values;

void read_input() {
    ifstream fin("rucsac.in");

    fin >> N >> G;
    values = vector<pair<int, int>>(N + 1);
    for (int i = 1 ; i <= N ; i++) {
        fin >> values[i].first >> values[i].second;
        cout << values[i].first << " " << values[i].second << endl;
    }
}

void solve() {
    read_input();
    vector<vector<int>> dp(N + 1, vector(G + 1, 0));
    for (int i = 1 ; i <= N ; i++) {
        for (int j = 1 ; j <= G ; j++) {
            if (j >= values[i].first)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - values[i].first] + values[i].second);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    write_output(dp[N][G]);
}

void write_output(long long res) {
    ofstream fout("rucsac.out");
    fout << res;
}

};

int main() {
    solution sol;
    sol.solve();
}