#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];
    for (int i=1; i<=N; i++){
        for (int cw=0; cw<=G; cw++){
            D[i % 2][cw] = D[(i-1) % 2][cw];
            if(W[i]<=cw){
                D[i % 2][cw] = max(D[(i-1) % 2][cw],D[(i-1) % 2][cw-W[i]]+P[i]);
            }
        }
    }
    g << D[N % 2][G];
}