#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]);
        }
}

/*
void dinamica () {
    for (int i=1; i<=n; i++)
        for (int j=1; j<=gmax; j++) {
            if (greutate[i]>j) best[i][j]=best[i-1][j];
            else best[i][j]=max(best[i-1][j-greutate[i]]+castig[i], best[i-1][j]);
        }
}

void scrieMatrice () {
    for (int i=1; i<=n; i++){
        for (int j=1; j<=gmax; j++) cout<<best[i][j]<<' ';
        cout<<endl;
    }
}


void reconstituie (int i, int j) {
    if (i*j!=0) {
        if (best[i][j]==best[i-1][j-1]) reconstituie (i-1, j-1);
        else {
            reconstituie (i-1, j-greutate[i]);
            cout<<i<<' ';
        }
    }
}
*/

int main () {
    citeste ();
    dinamica ();
    //scrieMatrice ();
    //reconstituie (n, gmax);
    g<<best[gmax]<<'\n';
    return 0;
}