#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g, w, p, maxProfit;
int we[5005], pr[5005];
int d1[10001], d2[10001];
void citire() {
    fin >> n >> g;
    for (int i = 0; i < n; ++i) {
        fin >> we[i] >> pr[i];
    }
}
void egalare() {
    for (int i = 0; i <= g; ++i) {
        d1[i] = d2[i];
        //d2[i] = 0;
    }
}
int main()
{
    citire();
    for (int i = 0; i < n; ++i) {
        w = we[i];
        p = pr[i];
        for (int j = w; j <= g; ++j) {
            d2[j] = max(d1[j], d1[j - w] + p);
            if (d2[j] > maxProfit) {
                maxProfit = d2[j];
            }
        }
        egalare();
    }
    fout << maxProfit << '\n';
    return 0;
}