#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

#define Nmax 5005
#define Gmax 10005

int N, G;
int D1[Gmax], D2[Gmax];
int W[Nmax], P[Nmax];

int main()
{
    f >> N >> G;
    for (int i=1; i<=N; i++) f >> W[i] >> P[i];
    for (int i=1; i<=N; i++){
        for (int cw=0; cw<=G; cw++){
            D2[cw] = D1[cw];
            if(W[i]<=cw){
                D2[cw] = max(D1[cw],D1[cw-W[i]]+P[i]);
            }
        }
        swap(D1,D2);
    }
    g << D1[G];
}