#include <fstream>
#define nmax 5000

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
unsigned int PD[nmax][nmax], Gr[nmax], Pr[nmax], G, N;
inline int maxim(int a, int b){
    return (a > b) ? a : b;
}
int main()
{unsigned int i, j;
    f>> N>> G;

    for(i = 1; i <= N; ++i)
        f>> Gr[i]>> Pr[i];
    for(i = 0; i <= G; ++i){
            PD[1][i] = 0;
         if(Gr[1] <= i) PD[1][i] = maxim(PD[1][i], (PD[0][i - Gr[1]] + Pr[1]));
    }
    j = 2;
    while(j <= N){
        for(i = 0; i <= G; ++i){
            PD[2][i] = PD[1][i];
         if(Gr[j] <= i) PD[2][i] = maxim(PD[2][i], (PD[1][i - Gr[j]] + Pr[j]));
        }
        for(i = 1; i <= G; ++i)
            PD[1][i] = PD[2][i];
        ++j;
    }
    g<< PD[2][G]<<'\n';
    return 0;
}