#include <fstream>
///Varianta 2
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX = 5000,
          GMAX = 10000;
int W[NMAX + 1], P[NMAX + 1],
    D[GMAX + 1];
int main()
{
    int N, G, Pmax = 0, i;
    f >> N >> G;
    for(i = 1; i <= N; ++i)
        f >> W[i] >> P[i];
    for(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;
}