#include <iostream>
#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;
}