#include <fstream>
#include <iostream>
#define N 5000
#define G 10001

using namespace std;

int C[2][G];
short W[N], P[N];

int main() {
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n, g;
    fin >> n >> g;
    for (int i = 0; i < n; ++i)
        fin >> W[i] >> P[i];

    int k = 1;
    for (int i = 0; i < n; ++i, k ^= 1) {
        for (int j = 1; j < W[i]; ++j)
            C[k][j] = C[k ^ 1][j];
        for (int j = W[i]; j <= g; ++j)
            C[k][j] = max(C[k ^ 1][j - W[i]] + P[i], C[k ^ 1][j]);
    }

    fout << C[k ^ 1][g] << "\n";

    return 0;
}