#include <fstream>
#define MAX_OBJECTS 5000
#define MAX_WEIGHT 10000
using namespace std;

int w[MAX_OBJECTS + 1], profit[MAX_OBJECTS + 1];
int n, G, lc, lp;

int dp[2][MAX_WEIGHT + 1];

int main() {
    int lc, lp;
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    lc = 1;
    lp = 0;

    fin >> n >> G;

    for (int i = 0; i < n; ++i) {
        fin >> w[i] >> profit[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= G; ++j) {
            if (j - w[i - 1] >= 0) {
                dp[lc][j] = std::max(dp[lp][j - w[i - 1]] + profit[i - 1], dp[lp][j]);
                // dp[i][j] = std::max(dp[i - 1][j - w[i - 1]] + profit[i - 1], dp[i - 1][j]);
            }
            else {
                // dp[i][j] = dp[i - 1][j];
                dp[lc][j] = dp[lp][j];
            }
        }

        lc = 1 - lc;
        lp = 1 - lp;
    }

    fout << dp[lp][G] << "\n";

    fin.close();
    fout.close();
    return 0;
}