#include <fstream>
using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");

const int NMAX = 5000,
          GMAX = 10000;
int W[NMAX+1], P[NMAX+1];
int D[2][GMAX+1];

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