#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");

int n, gmax, greutate[5001], castig[5001], best[10001];

void citeste () {
    f>>n>>gmax;
    for (int i=1; i<=n; i++) f>>greutate[i]>>castig[i];
}

void dinamica () {
    for (int i=1; i<=n; i++)
        for (int j=gmax; j>=1; j--) {
            if (greutate[i]<=j)
                best[j]=max(best[j-greutate[i]]+castig[i], best[j]);
        }
}
int main () {
    citeste ();
    dinamica ();
    g<<best[gmax]<<'\n';
    return 0;
}