#include <fstream>
const int NMAX = 5005;
const int GMAX= 10005;
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N, G, D[2][GMAX], W[NMAX], P[NMAX];
int main() {

    int i, j;
    fin>>N>>G;
    for(i=1; i<=N; i++)
        fin>>W[i]>>P[i];
    for(i=1; i<=N; i++)
        for(j=1; j<=G; j++) {
            D[i%2][j]=D[(i-1)%2][j];
            if(W[i]<=j)
                D[i%2][j]=max(D[(i-1)%2][j], D[(i-1)%2][j-W[i]]+P[i]);
        }
    fout<<D[N%2][G]<<'\n';
    return 0;
}