/**
/// Varianta 1
#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;
}
*/

/// Varianta 2
#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[GMAX+1];

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