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

#define Nmax 5005
#define Gmax 10005

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