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

#define Nmax 5005
#define Gmax 10005

int N, G;
int D[2][Gmax];
int W[Nmax], P[Nmax];

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